3

2つの配列間の類似性を計算するための最もよく知られているアルゴリズムの計算の複雑さは何ですか（DNAまたはタンパク質アラインメント/近似文字列マッチングなど）？

類似性は以下に基づいています：

  1. 置換スコアリングマトリックスを使用してアラインメントをスコアリングします（タンパク質アルファベットの20シンボルまたはDNAアルファベットの4シンボルのグローバルまたは位置固有の置換の場合）

  2. ギャップペナルティ

BowtieおよびBWAショートリードアライナーで使用されるBurrows–Wheeler変換の線形時間は、実際の最先端のものですか、それとも同じ問題を解決する劣線形アルゴリズムがありますか？

[編集]：参照データセットの前処理/インデックス付けを想定して劣線形になる近似マッチングにLSHを適用することを考えています

4

1 に答える 1

1

ある時点でシーケンス全体を読み取ることになると思うので、サブリニア時間アルゴリズムはあり得ません。

于 2013-02-09T03:14:12.910 に答える