長いギャップを可能にする最適なシーケンスアラインメント

長い挿入と削除を可能にする最適なシーケンスアラインメントのための新しいアルゴリズムが開発されます。アルゴリズムには、O（（L+C）MN）計算ステップ、O（LN）プライマリメモリおよびO（MN）セカンダリメモリストレージが必要です。ここで、MおよびN（N以上のM）はシーケンス長です（通常はL）l 3未満または大きいl）は、ギャップの重み付け関数を指定するセグメントの数であり、Cは定数です。また、以前のTracebackアルゴリズムを変更して、指示されたグラフのコンパクトな形式のすべての最適なアライメントのみを見つけます。現在のバージョンは、一連のアラインされたシーケンスを入力として受け入れ、いくつかの反復手順により複数のシーケンスアラインメントを容易にします。

A new algorithm for optimal sequence alignment allowing for long insertions and deletions is developed. The algorithm requires O((L+C)MN) computational steps, O(LN) primary memory and O(MN) secondary memory storage, where M and N(M greater than or equal to N) are sequence lengths, L(typically L less than or greater than 3) is the number of segment specifying the gap weighting function, and C is a constant. We have also modified our earlier traceback algorithm so that it finds all and and only the optimal alignments in a compact form of a directed graph. The current versions accept a set of aligned sequences as input, which facilitates multiple sequence alignment by some iterative procedures.