アメリエフのブログ

Amelieff Staff Blog

アライメントのアルゴリズム

次世代シーケンサの解析を行う際、アライメントという作業を行います。

本日は、アライメントツールとしてbwaを例にとり、アライメントのアルゴリズムに関して記述していきます。
よろしくお願いします。


bwaのInformationでは、Burrows-Wheeler Transform (BWT)をベースとしたアルゴリズムが組まれています(コチラを参照)。

さらに、bwaでアライメントを行うと、“calculate SA coordinate”と表示されます。

BWTって・・・?
SA(Suffix Array)とは・・・?

ということで下記のHPを参考にし、ゲノム配列に置き換えて考えてみました。

wiki ブロックソート
Burrows Wheeler TransformとSuffix Array
Suffix Arrayの概念

大量のデータを用いて検索を行う際に、用いられる方法のようです。
DNA断片の配列を繰り返し並列で並べ、印を付ける(index化)。
その後、ソートを行うことで、SAを作成することができるようです。



今日はここまでです!