 | This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. (June 2024) |
| FSA | |
|---|---|
| 開発者 | ロバート・ブラッドリー（カリフォルニア大学バークレー校）、コリン・デューイ（ウィスコンシン大学マディソン校）、リオル・パクター（カリフォルニア大学バークレー校） |
| 安定版リリース | 1.5.2
|
| オペレーティングシステム | UNIX、Linux、Mac |
| タイプ | バイオインフォマティクスツール |
| ライセンス | オープンソース |
高速統計アライメント（FSA）は、多数のタンパク質、RNA、または長いゲノムDNA配列をアライメントするための多重配列アライメントプログラムです。MUSCLEやMAFFTと並んで、FSAは数百または数千の配列データセットをアライメントできる数少ない配列アライメントプログラムの一つです。FSAは、他のプログラムとは異なる最適化基準を用いることで、非相同配列をより確実に識別できますが、この精度の向上は速度の低下を伴います。
FSA は現在、新しい線虫ゲノムの配列決定やハエにおける生体内転写因子結合の 分析など、複数のプロジェクトに使用されています。
入出力
このプログラムはFASTA形式の配列を受け入れ、 FASTA形式またはストックホルム形式でアライメントを出力します
アルゴリズム
入力配列を整列させるアルゴリズムには、4つのコアコンポーネントがあります
事後確率を生成するためのペア隠れマルコフモデル
このアルゴリズムは、まず、アラインメント対象の配列プールからランダムに抽出した任意の2つの配列間のアラインメント事後確率を決定することから始まります。各列の事後確率は、配列ペア間のアラインメント確率の予測を補強するとともに、アラインメントの信頼性が低い可能性のある列を除外します。これらの確率は、任意の配列ペア間の相同性の予測と推定にも役立ちます。任意の2つの入力配列のアラインメント事後確率を決定するために、標準的な5状態ペア隠れマルコフモデル（ペアHMM）が使用されます。ペアHMMモデルは、2つのアラインメントされた配列間のシンボルの削除と挿入を考慮するために、2セットの削除（D）状態と挿入（I）状態を使用しますが、精度を大幅に損なうことなく3つの状態を持つこともできます。
任意の2つの配列ペアの事後確率分布を決定するために必要なペアワイズ比較の回数は計算コストが高く、アラインメント対象の配列数の2乗に比例するため、エルデシュ・レーニのランダムグラフ理論に着想を得たランダム化手法を用いることで、この回数を削減できます。これにより、データセットの実行時間と多重アラインメント実行の計算コストが大幅に削減されます。
確率の統合
シーケンスペアの各列の事後確率は、最急上昇アルゴリズムを使用する重み付け関数を使用してソートされます
配列アニーリング
多重配列アライメントアルゴリズムを実行する既存のプログラムのほとんどは、プログレッシブアライメントに基づいています。このプロセスは、配列が全くアライメントされていない状態である「ヌルアライメント」から始まります。その後、配列プールは、ペアワイズ比較、または部分配列の部分アライメントペアのアライメントによってアライメントされます。このプロセスは、結果として得られる多重配列アライメントが、開始時にアライメントされた配列に大きく依存する可能性があるため、アライメントに問題を引き起こす可能性があります。MSAを修正できるような、以前にアライメントされた配列の再アライメントは行われません。
FSAはこの問題を克服するために、配列アニーリング技術を用います。ソートされた事後確率は、配列アニーリング技術と組み合わせて多重アライメントを生成します。この技術は、真の配列への期待距離を最小化する2つの配列間のアライメントを見つけます。この場合、2つの配列間の距離とは、一方の配列の文字がもう一方の配列の同じ列の文字と相同でない列の数です。
配列アニーリング法は、真の配列への期待距離が最小となるアライメントを決定することで、逆に、期待精度が最大となるアライメントを見つけます。アライメントの精度は、「真の」アライメントを基準として、配列が相同となる列の割合を示します。この精度は、アライメントされていない配列（ヌルアライメント）から開始し、アライメントの精度が増加するにつれて異なる列の文字をアライメントする目的関数として使用されます。
アライメントの順序
FSAは、インデルや置換を厳密に考慮するのではなく、列内の相同性に基づいて複数の配列をアラインメントします。そのため、FSAは、両方のアラインメントの配列上のすべての位置において相同性について同じ記述ができる場合、アラインメントを同等とみなします。例えば、ペアワイズ比較において、2つのアラインメントの特定の位置にギャップがある場合、比較対象の2つの配列はその位置において相同ではないと言えます。この結果、ギャップオープンイベントが異なるにもかかわらず、同等とみなされるアラインメントが生成される可能性があります。そのため、FSAは「ギャップオープン」が最小限となるアラインメントを出力することを選択します。
並列化
非常に大きなデータセットを処理するために、FSAは必要なすべてのペアワイズ比較とアライメントの実行を異なるプロセッサに分割することができます。これは、利用可能な各プロセッサにペアワイズ比較をチャンク単位で分散する「固定サイズチャンク化」戦略を使用して処理されます。したがって、各プロセッサは、収集されたデータをシーケンスアニーリングのために単一のプロセッサにマージする前に、ペアワイズ比較のチャンクに対して事後確率計算を実行できます
視覚化
FSAによる多重配列アライメントの結果は、FSA独自のGUIに表示できます。GUIは、アライメント自体の文字列の列に、アライメント品質のさまざまな指標を表示し、色分けすることができます。FSAモデルで観察でき、近似できる5つの異なる指標には、精度、感度、確実性、特異度、一貫性があります
他のプログラムとの比較
FSAは、タンパク質（SABmark 1.65およびBAliBASE 3）、RNA（BRAliBase 2.1およびConsanmix80）、およびDNA配列の多重アライメントデータベースと比較評価されました。これらのベンチマークは、ClustalW、MAFFT、MUSCLE、T-Coffeeなどの他の一般的なアライメントプログラムと並行して実施されました。全体として、FSAの抄録と研究論文がレビューのために受領された時点で、FSAは精度と陽性予測値においてほとんどのアライメントプログラムを上回り、感度はMAFFTやProbConsRNAなどのより高性能なプログラムと同等でした。16Sリボソーム配列のアライメントにかかる時間を比較することにより、実行時間の比較も実施されました。MAFFTは他のアライメントプログラムよりも高速にアライメントを実行し、MUSCLEとFSA（3状態HMMを使用し、反復改良を無効にした場合）が次に高速なプログラムでした。
参考文献
Bradley RK, Roberts A, Smoot M, Juvekar S, Do J, Dewey C, Holmes I, Pachter L (2009). 「高速統計アライメント」. PLOS Computational Biology . 5 (5) e1000392. Bibcode : 2009PLSCB...5E0392B. doi : 10.1371/ journal.pcbi.1000392 . PMC 2684580. PMID 19478997
Schwartz AS, Pachter L (2007)「配列アニーリングによる多重アライメント」バイオインフォマティクス 23: e24-9.
Eddy SR. 隠れマルコフモデルを用いた多重アライメント. Proc Int Conf Intell Syst Mol Biol. 1995;3:114-20. PMID 7584426.
外部リンク
- FSAウェブサーバー
- FSAソースコード
