DNA配列の編集距離を計算する

Question

したがって、2つのDNA配列の間の最低コストを調整する作業が与えられています。失敗入力の1つは、適切なアライメントが24コスト

CGCAATTCTGAAGCGCTGGGGAAGACGGGT & TATCCCATCGAACGCCTATTCTAGGAT 

ですが、私は23

のコストを取得していますそして、私は塩基がAを言うのスイッチングコストを読まなければならない - > T、G - > Cなどなど、私が与えられているコストのファイルは、私がどのように見える完全にすべての拠点を結ぶPythonの辞書を作ってきた

*,-,A,T,G,C 
-,0,1,2,1,3 
A,1,0,1,5,1 
T,2,1,0,9,1 
G,1,5,9,0,1 
C,3,1,1,1,0 

です。

{'AT': '1', '-C': '3', 'TG': '9', '-G': '1', 'AC': '1', 'C-': '3', 'CA': '1', 'AA': '0', '--': '0', 'TA': '1', 'T-': '2', 'CG': '1', '-T': '2', 'CC': '0', 'GG': '0', 'A-': '1', 'CT': '1', 'AG': '5', 'GC': '1', 'GT': '9', 'GA': '5', 'G-': '1', '-A': '1', 'TC': '1', 'TT': '0'} 

現在、私の実装はいくつかのケースのために働く、それ以外の場合には、私はここで+/- 1

ではオフにしています私のコードのスニペット

def align(one_Line, costBook): 
    Split_Line = one_Line.split(",") 
    array = [[0] * len(Split_Line[1]) for i in Split_Line[0]] # Zero fill array, 

    xLine = Split_Line[0] 
    yLine = Split_Line[1] 

    for i in range(1, len(xLine)): 
     array[i][0] = array[i - 1][0] + int(costBook['-' + xLine[i - 1]]) 
    for i in range(1, len(yLine)): 
     array[0][i] = array[0][i - 1] + int(costBook[yLine[i - 1] + '-']) 

    for i in range(1, len(xLine)): 
     for j in range(1, len(yLine)): 
      array[i][j] = min(array[i - 1][j] + diff('-', xLine[i], costBook), 
           array[i][j - 1] + diff(yLine[j], '-', costBook), 
           array[i - 1][j - 1] + diff(yLine[j], xLine[i], costBook)) 

差分機能でありますは

def diff(x, y, cost): 
    if x == y: 
     return 0 
    keyStr = x + y 
    return int(costBook[keyStr]) 

私は間違っていますか？それは実際の配列自体に埋め込まれているのでしょうか、あるいはベースケースを間違っていますか？先進的な感謝！

編集： 半編集版ですが、少なくとも編集費用がかかります。

AGTTGTGAAAGAACAAGCGCACAATATTGCCGCGCCGAAAGCT,TTCTTTCATTATTCAA‌​ATGTATAGTTTAGAGCGTTA‌​A 

Answer 1

私はあなたのアルゴリズムが失敗している理由は、あなたの配列（スコアリングマトリックス）の "ギャップ"行について考慮していないと考えています。

AおよびBの2つのシーケンスを考えてみましょう。各シーケンスの長さはnです。 Needleman-WunschアルゴリズムとSmith-Watermanアルゴリズムに関するウィキペディアの記事を見ると、それぞれの「スコアリング」マトリックスには先頭に余分な行があることがわかります。これは、AまたはBの最初の文字をギャップとペアにすることを表します。あなたはこの追加の行を含めていません

array = [[0] * len(Split_Line[1]) for i in Split_Line[0]] 

：私はあなたがすぐとして、あなたの配列を定義するとき、私は

何を意味するかを確認するために、これらのページを見直しお勧めします。

この余分な行を追加し、スコアを計算するロジックを変更するには、align関数を変更する必要があります。すなわち：

def align(one_Line, costBook): 
    Split_Line = one_Line.split(",") 

    # Defining an array with an extra row and col to represent a leading gap 
    array = [[0] * (len(Split_Line[1])+1) for i in range(len(Split_Line[0])+1)] # Zero fill array, 

    xLine = Split_Line[0] 
    yLine = Split_Line[1] 

    # Changed so we include our extra line in the loop 
    for i in range(1, len(xLine)+1): 
     array[i][0] = array[i - 1][0] + int(costBook['-' + xLine[i - 1]]) 
    for i in range(1, len(yLine)+1): 
     array[0][i] = array[0][i - 1] + int(costBook[yLine[i - 1] + '-']) 

    # Changed so we include our extra row/col in the loop 
    for i in range(1, len(xLine)+1): 
     for j in range(1, len(yLine)+1): 
      # The references to the original string now need -1 (i.e. i-1) 
      array[i][j] = min(array[i - 1][j] + diff('-', xLine[i-1], costBook), 
           array[i][j - 1] + diff(yLine[j-1], '-', costBook), 
           array[i - 1][j - 1] + diff(yLine[j-1], xLine[i-1], costBook)) 
    return array