読者です 読者をやめる 読者になる 読者になる

tak0kadaの医学メモ

発声練習、生存確認用。

数理統計関連は 何でもノート

リファレンスへのアラインメント(RNA-seq)

シーケンサーで得られたリードを既知のゲノム配列をリファレンスとしてマッピングすることを考える。この過程での問題点は得られるリードが短いこと、多数あること、ゲノムが類似の配列(リピートや偽遺伝子)を含むこと、ゲノムの多様性やシーケンスの際の失敗によるミスマッチの存在、挿入欠失があり、RNAの場合さらにイントロンのため連続してマップされない可能性があることが挙げられる。(以下粗雑なメモ)

  • 任意の塩基のマッピングの質は
    Q = -10log10P
    で計算されるQ値というものを用いることが一般的らしい。ここでPはリードが他の部分に対応する確率を表す。定義から明らかだが、Q値が大きいほど信頼性が高く、小さいほど低い。
    (参考: http://jp.illumina.com/science/education/sequencing-quality-scores.html)

  • RNA-seqのアラインメントの際にはスプライシングを考慮することでプログラム選択が行われることが多いらしい。スプライシングを無視する場合はBWA、Bowtie、考慮する場合はTopHat、STAR、GSNAPというプログラムが使われているらしい。

  • バイオインフォマティクス入門(https://www.amazon.co.jp/バイオインフォマティクス入門-日本バイオインフォマティクス学会/dp/4766422511)によると配列のアラインメントを行うアルゴリズムとして

    • k-merをハッシュ表を用いて検索する方法
    • Burrows-Wheeler変換後の文字列を用いたFM-indexを利用する方法 が挙げられている。
  • アルゴリズムとは:
    問題を解くための手順を定式化した形で表現したもの。プログラマアルゴリズムを考慮するときには計算量やメモリ消費量を気にしている。計算量が多いと計算に時間がかかる。また、メモリ消費量が多い場合PCの限界までは良いが、限界を超えた瞬間計算不能になってしまう。このテキストで紹介されるアルゴリズムはハッシュを利用することで表のアクセス時間を線形時間に抑えたり、リファレンスの圧縮によってメモリ消費量を減らす戦略になっている。計算時間に関しては計算機を並列に使うことでも短縮できる。

  • ハッシュとは:
    ハッシュ関数は要約関数とも呼ばれる。あるデータが与えられた場合にそのデータを代表する数値を得る操作、または、その様な数値を得るための関数のこと。例えば4-merを検索するとしてACGTに10を割り当てた場合、表の10番目のところの値を読み出すことにすると配列のアクセス時間を短縮できる。

■BWA(Burrows-Wheeler Aligner)
http://bio-bwa.sourceforge.net/が検索でヒットした

■BowtieとTopHatについて
Bowtieはアラインメントを行うアルゴリズム(プログラム)、TopHatはBowtieを内部で利用してスプライシングを考慮したアラインメントを計算するプログラム。FM-index、Burrows-Wheeler Transformを利用する。

■ FM-index
■ Burrows-Wheeler Transform
可逆変換。圧縮アルゴリズムは基本的にjpegのような不可逆なものか、zipのような可逆なものに分かれる。確か情報理論の分野によると、データを可逆に圧縮するためにはデータに何らかの偏りや規則性が必要。
アルゴリズムの詳細については
http://shogo82148.github.io/homepage/memo/algorithm/suffix-array/introduction.html
http://d.hatena.ne.jp/naoya/20081016/1224173077
http://qiita.com/erukiti/items/f11f448d3f4d73fbc1f9
が分かりやすい。