LCS（最長共通部分列）アルゴリズムの応用

前回の記事でLCSを求めましたが、DNA断片を組み立てる際に応用できそうです。

最長共通配列LCS探索アルゴリズム

以下のアルゴリズムを用いることで、２つの配列のうち最も長くオーバーラップする部分を瞬時に見つけることができます。

def lcs(seq1,seq2):
    t_1 = ''
    t_2 = ''
    for i in range(len(seq1)):
        if seq1[:i] == seq2[-i:]:
            t_1 = seq1[:i]
    for i in range(len(seq2)):
        if seq2[:i] == seq1[-i:]:
            t_2 = seq2[:i]
    if len(s_1) >= len(s_2):
        return t_1
    elif len(s_1) < len(s_2):
        return t_2
    else:
        pass

最長のオーバーラップした部分をつなぎ合わせる作業を繰り返していくことで、DNA断片を組み立てることができます。

このアルゴリズムは、以下のDNA再構築アルゴリズムにも使用しています。