2

私はPythonを初めて使用し、1つのコードの速度を上げるのに苦労しています。

私は 50 万の DNA 配列を含む辞書を持っています。キーとして配列の識別子を持ち、値として対応する DNA 配列を持っています。これらの配列は、200 から 60k のヌクレオチドを持つ可変長 (CTACTA を含む単なる文字列です...) です。大きなシーケンスの部分文字列である DNA シーケンスを削除する必要があります。

私はこれを書きました：

def remove_subs():

    #Create a list of values based on reversed lenght
    LISTA=sorted(list(x for x in finaldic.values()), key=len, reverse=True)

    LISTA2=[]

    for a in range(len(LISTA)):
        #run the same list but in opposite direction 
        for b in range(len(sorted(LISTA,key=len))):
            if len(LISTA[b])<len(LISTA[a]):
                if LISTA[a].find(LISTA[b])!=-1 or Bio.Seq.reverse_complement(LISTA[a]).find(LISTA[b])!=-1 and LISTA[b]!=LISTA[a]:
                    LISTA2.append(LISTA[a])

組み込みの .find を使用して反対方向に、DNA シーケンスのみを含むリスト (長さ順) の 2 つの for ループを実行して、これらの部分文字列シーケンスを識別しようとしています。

このコードは完全に機能しますが、そのような量の情報を実行するには時間がかかります。より高速なオプションが存在すると確信しています。

手伝ってくれますか？

4

5 に答える 5

1

アルゴリズムの観点からは、サフィックス ツリーを確認する必要があります。まず、調べたい文字列から一般化されたサフィックス ツリーを作成します。これは、構築するのに O(n) 時間の複雑さがあります (n = 検索するすべての文字列の文字数)。次に、そのツリーにクエリを実行し、その中に部分文字列が含まれているかのように、O(m) 時間の複雑さを持ちます。ここで、m は部分文字列の長さです。これは、本質的に、可能な限り高速です。

いくつかのサフィックス ツリー ライブラリを説明するスタック オーバーフローの質問:

python: 一般化されたサフィックス ツリーのライブラリ

残念ながら、ここにある例はそれほど成熟したコードベースではありません...最適化などに重点を置いた C ライブラリがあります。それにもかかわらず、次のサフィックス ツリー アルゴリズムのようなものは、コードの簡単なドロップイン置換である必要があります。

import SubstringDict
d = SubstringDict.SubstringDict()
d['foobar'] = 1  
d['barfoo'] = 2
d['forget'] = 3
d['arfbag'] = 4

print(d['a'])
# [1, 2, 4]
print(d['arf'])
# [2, 4]
print (d['oo'])
# [1, 2]
print(d['food'])
# []

文字列の検索と照合は、バイオインフォマティクスにおいて非常に大きく活発な分野であり、この問題に関する文献は数多くあります。

于 2013-11-08T20:14:11.180 に答える
0

速度を上げる可能性のある修正をいくつか紹介します。少なくとも、コードは Python にとってより慣用的なものになります。

def remove_subs():

    #Create a list of values based on reversed lenght
    list_a=sorted((x for x in finaldic.values()), key=len, reverse=True)

    list_a_2=[]

    for a in list_a:
        #run the same list but in opposite direction 
        for b in sorted(list_a,key=len):
            if len(b)<len(a):
                if b in a or b in Bio.Seq.reverse_complement(a) and b!=a:
                    list_a_2.append(a)

2 つの主な変更点: 1) メソッドを使用する代わりに、.findpython のin演算子を使用して検索しています。2) リストにインデックスを付ける代わりに、それらを直接ループします。

それが真実ではない場合、決して入ることはないので、おそらくif len(b) < len(a)条件を回避することができます.ba

于 2013-11-08T19:48:18.030 に答える
0

テスト データや自己完結型のコードがないため、テストが難しくなりますが、ループ内での並べ替えが良いアイデアになることはめったにないことを指摘しておきます。これにより、実行時間が O(n^3 * logn) から O(n^2) に短縮されます。

def remove_subs():
    list_a_backward = sorted(list(x for x in finaldic.values()), key=len, reverse=True)
    list_a_forward = list_a_backward
    list_a_forward.reverse()

    matches = []
    for first in list_a_backward:
        for second in list_a_forward:
            if first in second or first in Bio.Seq.reverse_complement(second):
                matches.append(first)
                break

純粋な python を実行しているように見えるので、Pypy も試すことができます。それができない場合は、numba または Cython が役立つ場合があります。

于 2013-11-08T21:27:58.510 に答える
0

シーケンスのハッシュについてはどうですか？最小シーケンスの長さが 200 の場合、ウィンドウ サイズが 200 のローリング ハッシュ ( http://en.wikipedia.org/wiki/Rolling_hash ) を実行します。次に、ハッシュを辞書のキーとして使用します。 、シーケンス識別子のリストを保持します。次に、サイズ > 1 のリストがある場合、それは部分文字列の候補であり (衝突が発生する可能性があります)、find を使用できます。

于 2013-11-08T21:01:22.957 に答える