ステムロック

バイオインフォマティクスにおいて、Stemlocは、ペア確率文脈自由文法(確率文脈自由文法とも呼ばれる)として知られるRNA 構造の確率モデルに基づいて、複数の RNA 配列のアラインメントとRNA 構造の予測を行うオープンソース ソフトウェアです。Stemloc は、同じ目的を持つ以前の方法と比較して時間と空間のコストを削減しながら、RNA 配列の構造を同時に予測してアラインメントしようとします。結果として得られるソフトウェアは、フォールド制約とアラインメント制約の両方を導入することで、Sankoff アルゴリズムの制約バージョンを実装します。これにより、プロセッサとメモリの使用量が減少し、汎用ハードウェアでより大きな RNA 配列を分析できるようになります。Stemloc は、2004 年に Ian Holmes によって作成されました。

Stemloc は、DART ソフトウェア パッケージの一部としてダウンロードできます。入力ファイルはFASTA形式またはStockholm 形式で受け付けられます。

• フォールド: RNA フォールディングは、RNA 分子が分子内相互作用を通じて二次構造を獲得するプロセスです。
• フォールドエンベロープ: アルゴリズムで考慮される候補フォールドのセット
• アライメントエンベロープ: アルゴリズムで考慮される候補アライメントのセット

1985 年に David Sankoff が開発したアルゴリズムでは、動的プログラミングを使用して、複数の RNA 構造を同時に整列させ、予測します。Sankoff アルゴリズムは、ビッグ O 表記 では時間と空間を、長さ のシーケンスではそれぞれ消費します。これは明らかにコストがかかるため、Stemloc のようなより優れた RNA 分析ツールを作成する動機となっています。Stemloc の最初の目標は、確率的文脈自由文法 (SCFG) スコアリング スキームを使用し、Sankoff アルゴリズムの制約バージョンを実装することで、2 つの RNA シーケンスの同時整列と構造予測にかかる時間と空間のコストを削減することでした。 ${\displaystyle O(L^{3N})}$${\displaystyle O(L^{2N})}$${\displaystyle N}$${\displaystyle L}$

Stemloc は、アライメント エンベロープとフォールド エンベロープを使用して、比較するシーケンスのアライメントと二次構造の両方を同時に制約します。フォールド エンベロープを使用すると、二次構造の検索を「整理」し、アルゴリズムで考慮できる 2 つの RNA シーケンスのサブシーケンスを決定できます。たとえば、特定の窒素結合塩基対を含めるか除外するかなどです。アライメント エンベロープを使用すると、アライメントの検索を「整理」し、2 つのシーケンスのアライメントで可能な「カットポイント」を決定できます。たとえば、特定の残基レベルの相同性を含めるか除外するかなどです。フォールド エンベロープはシーケンスごとに個別に事前計算され、アライメント エンベロープは二次構造を無視して 2 つのシーケンスを比較することによって事前計算されます。グローバルアライメントとローカルアライメントの両方がサポートされています。

Stemloc への入力は、FASTA 形式または Stockholm 形式のいずれかになります (それぞれの説明については上記を参照してください)。以下に入力例を示します。

stemloc  --local  dynalign.trna

「--local」コマンドは、ローカル アラインメント モードでファイルを分析します。「--global」を使用すると、グローバル アラインメント モードが使用されます。

この出力はストックホルム形式 です。シーケンス名、一致の座標、アラインメント、コンセンサス一次シーケンス、各シーケンスの二次構造、コンセンサス二次構造、およびビット単位のアラインメントのログオッズスコアが表示されます。「//」行は、アラインメントを区切ったり、ファイルの終わりを示すために使用されます。以下にサンプル出力を示します。

# ストックホルム 1.0 
#=GR RD0260/26-67 SS ..<<<<<.......>>>>>.....(<<<<.......>>>>). 
RD0260/26-67 			UACUCCCCUGUCACCGGGAGAGAAUGUGGGUUCAAAUCCCAUC
 #=GC PS_cons UAC..CCCUGUCACGG..G.GA..G.GGGUUC.AAUCCC..C 
RD0500/26-66 			UACGACCCUGUCACGGUCGUGA-CGCGGGUUCgAAUCCCGCC
 #=GR RD0500/26-66 SS ..<<<<<.......>>>>>...-.<<<<<.......>>>>>. 
#=GC SS_cons ..<<<<<.......>>>>>.....<<<<<.......>>>>>. 
#=GFSC31.872
//

Stemloc は、アルゴリズムのスコアリング スキームと見なすことができる確率的文脈自由文法に大きく依存しています。Sankoff のアルゴリズムは、すべての可能なフォールドとすべての可能なアラインメントを考慮するため、非常に正確で徹底的ですが、結果や出力を取得するにはかなりの時間がかかります。これを改善するために、Stemloc では、ユーザーが考慮するフォールドとアラインメントの合計数を制限できます。より具体的には、各シーケンスを時間内に個別に事前にフォールドし、時間内の二次構造を無視して事前にアラインメントすることができます。たとえば、以下の「-fast」コマンドを使用すると、すべての可能なフォールドを分析するのではなく、100 個の最良の RNA 構造のみが考慮されます。「-log DOTPLOT」コマンドを使用すると、フォールドとアラインメント エンベロープの視覚的な表現が出力されます。${\displaystyle O(L^{3})}$${\displaystyle O(L^{2})}$

stemloc  nanos-tiny.rna  -fast  -log  DOTPLOT

Stemloc の主なアイデアは、エンベロープを作成するためにサンプリングされる折り畳みとアラインメントの数のしきい値を設定できることです。これは、考慮される折り畳みとアラインメントの数を設定するオプション「-nf」と「-na」を使用して実行できます。(-1 を使用すると、サンプリングされる折り畳みとアラインメントの数が無制限になるため、両方のパラメーターに -1 を使用すると、入力データセットに対して Sankoff アルゴリズムが実行されます。)

Stemloc  nanos-tiny.rna  -nf  -1  -na  -1

Stemloc のもう 1 つの特徴は、データから確率的文脈自由文法などの確率モデルをパラメータ化できることです。Stemloc は、Inside-Outside アルゴリズムと確率的文脈自由文法を利用して、トレーニング セットの尤度を最大化します。これは、Stemloc のデフォルト パラメータが、 Rfam (データベース) バージョン 5.0の 30% から 40% のシーケンス同一性のペアワイズ アラインメントの選択に基づいてトレーニングされているため、便利です。ただし、これらのパラメータは常に効果的であるとは限りません。そのため、ユーザーとしてパラメータをトレーニングできることが役立ちます。

Stemloc はそれ以来、RNA 構造解析に関するさまざまな研究出版物で使用されてきました。最も顕著なのは、最適な多重配列アライメントの研究です。

• Holmes I. (2005) RNA構造進化の加速確率推論。BMCバイオインフォマティクス。2005年3月24日;6:73。
• Sankoff D. (1985) RNA の折り畳み、アラインメント、およびプロトシーケンスの問題の同時解決。SIAM 応用数学ジャーナル。1985 年 10 月;45:5。Sankoff D. (1985) RNA の折り畳み、アラインメント、およびプロトシーケンスの問題の同時解決。SIAM 応用数学ジャーナル。1985 年 10 月;45:5。

• Stemloc ホームページとチュートリアル