効率的なインプライドアラインメント

Efficient implied alignment.

• Alex J Washburn
• Ward C Wheeler

抄録

背景:

n個の葉からなるバイナリツリー[Formula: see text]が与えられ、各葉は最大でもkの長さの文字列でラベル付けされ、バイナリ文字列アライメント関数⊗が与えられると、[Formula: see text]の動的ホモロジーのアライメントを記述するために暗黙のアライメントが生成されます。これは最初に[Formula: see text]の各ノードを⊗を使ったアライメントコンテキストで装飾し、その後に続く順序前の探索の間に、それらの内部ノード装飾を使ってどの辺で挿入と削除のイベントが起こったかを推論することで行われる。

BACKGROUND: Given a binary tree [Formula: see text] of n leaves, each leaf labeled by a string of length at most k, and a binary string alignment function ⊗, an implied alignment can be generated to describe the alignment of a dynamic homology for [Formula: see text]. This is done by first decorating each node of [Formula: see text] with an alignment context using ⊗, in a post-order traversal, then, during a subsequent pre-order traversal, inferring on which edges insertion and deletion events occurred using those internal node decorations.

結果:

これまでの記述では、時間的に複雑な"バックプロパゲーション"の手法が提案されていたが、ここでは、時間的に複雑な"バックプロパゲーション"の手法について記述する。ここでは，時間的に複雑な暗黙的アライメントアルゴリズムを記述する［式：本文参照］．分子配列のように、十分に観測されたデータの場合、実行時間はベストケースの複雑さΩ(k∗n)に近づきます。

RESULTS: Previous descriptions of the implied alignment algorithm suggest a technique of "back-propagation" with time complexity [Formula: see text]. Here we describe an implied alignment algorithm with complexity [Formula: see text]. For well-behaved data, such as molecular sequences, the runtime approaches the best-case complexity of Ω(k∗n).

結論:

アルゴリズムの時間的複雑さが軽減されたことで、複数の配列アライメントを生成する際の有用性とヒューリスティックな有用性の両方が劇的に改善されました。

CONCLUSIONS: The reduction in the time complexity of the algorithm dramatically improves both its utility in generating multiple sequence alignments and its heuristic utility.