Bowtie は、数十塩基からなるショートリードの配列をリファレンス配列に照合し、リードをリファレンス配列にマッピングするプログラムである。Bowtie は、リファレンス配列を Burrows-Wheeler 変換（BWT）してインデックスを作成し、文字列の高速検索アルゴリズム（FM index）でマッピングを行なっている。既存の文字列検索アルゴリズムは、完全一致による検索となっているため、ミスマッチに対応できない。そこで、既存の文字列検索アルゴリズムに backtracking search および double indexing の概念を導入し、ミスマッチを許容できるようにしたのが Bowtie である。

検索アルゴリズム

Bowtie は、まずリードの塩基とリファレンス配列の塩基が完全一致するという前提で文字列検索を行う。完全一致でヒットする位置がなければ、Bowtie はリードの 5' 末端に存在する塩基のうち 1 つを他の塩基に置換して、再度検索を行う。これでもヒットしなければ、先ほどの置換した塩基を元に戻して、次に別の塩基を置換して、再度検索を行う。この操作（backtracking search）を、検索ヒットが現れるまでランダムに繰り返す。この操作をランダムに繰り返しているため、最初に見つけたヒットは最適なアラインメント位置であるとは限らない。Bowtie をデフォルトで使用するときは、ここに注意する必要がある。

Bowtie に -k, -a, または --best オプションをつけることによって、この問題を回避できる場合がある。例えば、-k 2 と指定すれば、Bowtie はランダム作業で検索ヒットした最初の 2 アラインメントを出力するようになる。また、-a を指定することで、Bowtie はすべての可能性を試して、すべてのアラインメントを出力するようになる。--best はすべての可能性を試して、その中から最適なアラインメントを出力させることができる。必要に応じてこれらのオプションを使用するとよい。

リードとリファレンス配列の間のミスマッチが 1 つだけであれば、backtracking search で検索することができる。しかし、そのミスマッチがリードの 3' 末端にあるとき、backtraking search の検索コストが非常に大きくなる。そこで、Bowtie では、リファンレンス配列を BWT 変換してインデックス（forward index）を作成するのに加えて、リファレンス配列の逆鎖に対しても同様にインデックス（mirror index）を作成している（逆相補鎖ではない！）。これにより、リードの 5' 末端の検索は forward index を使用し、リードの 3' 末端の検索は mirror index を利用することで、検索時間を減らす対策を行なっている。

リードとリファレンス配列の間にミスマッチが 2 つあるとき、Bowtie はリードの最初の 28 塩基（seed）に着目して検索を行う。まず、seed の最初の 14 塩基を hi-half、残りの塩基を lo-half に分ける。次に、2 つのミスマッチがともに hi-half に入っているのか、それとも 1 つが hi-half でもう 1 つが lo-half に入っているのかなどのケースを想定して、それぞれのケースに対して backtracking search を適用していく。

以上で見られるように、Bowtie は文字列検索アルゴリズムを拡張して、高速マッピングを可能にした。Bowtie は、複数のミスマッチを許容できるが、ギャップを許容するアルゴリズムが実装されていない。そのため、ギャップを含むようなアラインメントを見つけることができない。

Bowtie のインストール方法

Bowtie のソースコードをおよびコンパイル済み（バイナリー）のプログラムは SourceForge でダウンロードできる。バイナリープログラムをダウンロードした場合、展開するだけですぐに利用できる。

インデックス作成

Bowtie によるマッピングは、リファレンス配列のインデックスを使用する。このインデックスを作成するには bowtie-build コマンドを利用する。このコマンドに、リファレンス配列をの FASTA ファイルを -f オプションに与える。続けて、作成するインデックスの名前も合わせて与える。インデックスの名前を自由に決めることができ、次の例では Ensembl からダウンロードしたマウスのゲノム配列 Mus_musculus.GRCm38.68.fa を mus_bowtie_index の名前でインデックス化している。

bowtie-build -f Mus_musculus.GRCm38.68.fa mus_bowtie_index

このコマンドを実行すると、ディレクトリ中に mus_bowtie_index.1.ebwt、mus_bowtie_index.2.ebwt、mus_bowtie_index.3.ebwt、mus_bowtie_index.4.ebwt、mus_bowtie_index.rev.1.ebwt、mus_bowtie_index.rev.2.ebwt の 6 つのファイルが生成される。これら合わせて Mus_musculus.GRCm38.68.fa のインデックスとなる。

マッピング

FASTQ ファイル中のリードをリファレンス配列にマッピングするとき、bowtie コマンドを使用する。bowtie コマンドのあとに、オプション、インデックスの名前、FASTQ ファイル、出力ファイル名を順に指定する。次の例は、single-end RNA-Seq リードの mouse_ctrl.fq を mus_bowtie_index にマッピングして、その結果を mouse_ctrl.sam に保存している。

bowtie -S --best -p 4 mus_bowtie_index mouse_ctrl.fq mouse_ctrl.sam

paired-end リードの場合は、一般的に forward リードが mouse_ctrl_1.fq、reversed リードが mouse_ctrl_2.fq のように 2 つのファイルに保存されている。Bowtie を使用してマッピングを行うとき、-1 および -2 オプションでそれぞれのファイルを指定する。

bowtie -S --best -p 4 mus_bowtie_index -1 mouse_ctrl_1.fq -2 mouse_ctrl_2.fq mouse_ctrl.sam