アライメントフリー配列解析

FFP法は、配列中の各k -merの数を計算することから始まります（ヌクレオチド配列の場合、k -merの数は^{4k 、}タンパク質配列の場合、^20k）。各配列中の各k -merの数は、その配列中のすべてのk -merの合計数で割ることによって正規化されます。これにより、各配列が特徴頻度プロファイルに変換されます。次に、2つの配列間のペアワイズ距離は、それぞれのFFP間のJensen-Shannon（JS）ダイバージェンスによって計算されます。このようにして得られた距離行列は、近隣結合法、UPGMAなどのクラスタリングアルゴリズムを使用して系統樹を構築するために使用できます。

この方法では、与えられた配列内の各k merの出現頻度が計算されます。この方法の次の特徴的なステップは、マルコフ モデルを使用してこれらの頻度のランダムな背景を差し引いて、ランダムな中立突然変異の影響を減らし、選択的進化の役割を強調することです。正規化された頻度は、与えられた配列の構成ベクトル (CV) を形成するために固定された順序に配置されます。次に、コサイン距離関数を使用して、配列の CV 間のペアワイズ距離を計算します。このようにして得られた距離行列は、近隣結合法、UPGMAなどのクラスタリング アルゴリズムを使用して系統樹を構築するために使用できます。この方法は、効率的なパターン マッチングアルゴリズムを利用して、構成ベクトルの計算に以下を含めることで拡張できます。(i) 任意のk値のすべてのk mer、(ii) 任意に設定された最大k値までのすべての長さの部分文字列、(iii) すべての最大部分文字列。ここで、部分文字列を任意の文字で拡張すると出現回数が減少する場合、その部分文字列は最大です。^{[ 23 ] [ 24 ]}

RTD ベースの手法では、配列中の k mer の数を計算するのではなく、 k mer が再び出現するのに必要な時間を計算します。この時間は、特定のk merが連続して出現する際の残基数を指します。したがって、配列中の各k merの出現はRTD の形式で計算され、平均(μ) と標準偏差(σ) という 2 つの統計パラメータを使用して要約されます。したがって、各配列は、 4 ^{k 個}の RTD のμとσを含む2 ⋅ 4 ^kサイズの数値ベクトルの形式で表されます。配列間のペアワイズ距離は、ユークリッド距離尺度を使用して計算されます。このようにして得られた距離行列は、近隣結合法、UPGMAなどのクラスタリングアルゴリズムを使用して系統樹を構築するために使用できます。最近のアプローチであるパターン抽出エントロピー取得 (PEER) は、k mer の長さを直接検出し、エントロピーを使用して出現間隔を要約します。

FCGR法は、ゲノム配列のスケールに依存しない表現を提供するカオスゲーム表現（CGR）技術から発展したものです。^{[ 25 ]} CGRはグリッド線で分割でき、各グリッドの正方形は配列中の特定の長さのオリゴヌクレオチドの出現を示します。このようなCGRの表現は、周波数カオスゲーム表現（FCGR）と呼ばれます。これにより、各配列がFCGRで表現されます。配列のFCGR間のペアワイズ距離は、ピアソン距離、ハミング距離、またはユークリッド距離を使用して計算できます。^{[ 26 ]}

ほとんどのアライメントフリーアルゴリズムはシーケンスの単語構成を比較しますが、Spaced Words は、考慮位置と考慮しない位置のパターンを使用します。シーケンス内のスペース入りの単語の出現は、一致位置の文字のみによって定義され、考慮しない位置の文字は無視されます。このアプローチでは、入力シーケンス内の連続する単語の頻度を比較する代わりに、事前に定義されたパターンに従ってスペース入りの単語の頻度を比較します。事前定義されたパターンは、一致数の分散の分析^{[ 27 ]} 、複数のモデルでの最初の出現の確率^{[ 28 ]}、または期待される単語頻度と実際のアライメント距離の間のピアソン相関係数^{[ 29 ]によって選択できることに注意してください。}

このアプローチでは、選択された2つのシーケンス（長さがそれぞれnとmのシーケンスAとB ）について、一方のシーケンス（A）のある位置から始まり、もう一方のシーケンス（B）の任意の位置で完全に一致する最長部分文字列を特定します。このようにして、シーケンスAの異なる位置から始まり、シーケンスBのいくつかの位置に完全に一致する最長部分文字列の長さを計算します。これらの長さをすべて平均して、尺度を導き出します。${\displaystyle L(A,B)}$直感的に、${\displaystyle L(A,B)}$2 つの配列が似ているほど、${\displaystyle L(A,B)}$正規化されている[つまり]${\displaystyle L(A,B)/\log(m)}$]。これは、配列間の類似度を示します。

距離尺度を導出するために、類似度尺度の逆数を取り、そこから補正項を差し引いて、${\displaystyle d(A,A)}$ゼロになります。したがって

${\displaystyle d(A,B)=\left[{\frac {\log m}{L(A,B)}}\right]-\left[{\frac {\log n}{L(A,A)}}\right].}$

この措置${\displaystyle d(A,B)}$対称ではないので、計算する必要がある${\displaystyle d_{s}(A,B)=d_{s}(B,A)=(d(A,B)+d(B,A))/2}$これにより、2 つの文字列 (A と B) 間の最終的な ACS 尺度が得られます。^{[ 31 ]}部分列/部分文字列の検索は、接尾辞木を使用することで効率的に実行できます。^{[ 32 ] [ 33 ] [ 34 ]}

このアプローチはACSと密接に関連しており、ACSは最短の欠落部分文字列（ shustringと呼ばれる）を使用して2つのDNA配列間のサイトあたりの置換数を計算する。^{[ 35 ]}

これらのアプローチは、${\displaystyle D_{2}}$統計は、${\displaystyle k}$2 つの配列間の -mer マッチング。これらは単純な${\displaystyle D_{2}}$比較対象の配列の背景分布を考慮に入れることで統計を算出します。^{[ 36 ]}

これは、 MinHashボトムスケッチ戦略を使用してマルチセットのJaccard インデックスを推定する非常に高速な方法です。${\displaystyle k}$2 つの入力シーケンスの -mer。つまり、比率を推定します。 ${\displaystyle k}$-mer は合計数に一致します ${\displaystyle k}$配列の-mer。これは、比較対象の配列間の進化距離を推定するために使用でき、配列が最後の共通祖先から進化して以来の配列位置あたりの置換数として測定されます。^{[ 37 ]}

このアプローチでは、2 つのタンパク質配列間の距離値を、その数の減少に基づいて計算します。 ${\displaystyle k}$-mer が一致する場合${\displaystyle k}$増加する。^{[ 38 ]}

この方法は数を計算します${\displaystyle N_{k}}$の${\displaystyle k}$単語長または一致位置数の異なる値に対する-merまたはスペース付き単語一致（SpaM ）${\displaystyle k}$それぞれ、基となるパターンにおいて。アフィン線形関数の傾き ${\displaystyle F}$それは${\displaystyle N_{k}}$入力シーケンス間のジュークス・カントール距離を推定するために計算されます。^{[ 39 ]}

Skmer は、未アセンブルのシーケンスリードから種間の距離を計算します。MASH と同様に、 Jaccard 指数をセットに使用します。${\displaystyle k}$入力配列から-merを生成します。MASHとは対照的に、このプログラムはシーケンスカバレッジが低い場合でも正確であるため、ゲノムスキミングに使用できます。^{[ 40 ]}

この方法は、2 つの DNA 配列間で、両方の配列で 1 つの位置だけ離れたk -mer の一致のペアとして定義されるいわゆる構造を探索します。2 つのk -mer の一致はコンテキストと呼ばれ、それらの間の位置はオブジェクトと呼ばれます。Co-phylog は、オブジェクトの 2 つのヌクレオチドが異なる構造の割合を、2 つの配列間の距離として定義します。このアプローチは、未アセンブルのシーケンス リードに適用できます。^{[ 41 ]}

andi は、最大完全一致ワードによって挟まれたギャップのないローカルアライメントに基づいて、ゲノム配列間の系統発生距離を推定します。このようなワード一致は、サフィックス配列を使用して効率的に見つけることができます。完全一致ワード間のギャップのないアライメントは、ゲノム配列間の系統発生距離を推定するために使用されます。結果として得られる距離推定値は、位置あたり約 0.6 置換まで正確です。^{[ 42 ]}

FSWM は、いわゆるマッチ位置とドントケア位置を表す事前定義されたバイナリパターンPを使用します。入力 DNA 配列のペアに対して、Pに関してスペースワードのマッチを検索します。つまり、 Pのマッチ位置で一致するヌクレオチドとドントケア位置でのミスマッチの可能性のある、ギャップのない局所的なアライメントを検索します。偽の低スコアのスペースワードのマッチは破棄され、残りの相同なスペースワードのマッチのドントケア位置で互いにアライメントされたヌクレオチドに基づいて、入力配列間の進化距離が推定されます。 ^{[ 43 ]} FSWM は、未アセンブルの NGS リードに基づいて距離を推定するように適応されており、このバージョンのプログラムはRead-SpaMと呼ばれています。^{[ 44 ]}

Prot-SpaM（プロテオームベースのスペーシングワードマッチ）は、部分的または全体のプロテオーム配列に対するFSWMアルゴリズムの実装です。^{[ 45 ]}

Multi-SpaM ( Multiple Spaced -word Matches ) は、 FSWM のアイデアを複数の配列比較に拡張した、ゲノムベースの系統樹再構築のアプローチです。^{[ 46 ]}一致位置と不注意位置のバイナリパターンPが与えられると、プログラムはPブロック、つまりPの一致位置で一致するヌクレオチドを持ち、不注意位置でミスマッチの可能性がある、ギャップのないローカルな 4 方向アライメントを検索します。このような 4 方向アライメントは、入力ゲノム配列のセットからランダムにサンプリングされます。各 Pブロックについて、 RAxMLを使用してルートなしツリートポロジが計算されます。^{[ 47 ]}次に、プログラムQuartet MaxCut を使用して、これらのツリーからスーパーツリーを計算します。

塩基対相関（BBC）は、以下の式を用いてゲノム配列を固有の16次元数値ベクトルに変換します。

${\displaystyle T_{ij}(K)=\sum _{\ell =1}^{K}P_{ij}(\ell )\cdot \log _{2}\left({\frac {P_{ij}(\ell )}{P_{i}P_{j}}}\right)}$

の${\displaystyle P_{i}}$そして${\displaystyle P_{j}}$は、ゲノム中の塩基iとjの確率を表します。${\displaystyle P_{ij}(\ell )}$は、ゲノム内で距離ℓにある塩基iとjの確率を示します。パラメータK は、塩基iとj間の最大距離を示します。16 個のパラメータの値の変動は、ゲノムの内容と長さの変動を反映しています。^{[ 49 ] [ 50 ] [ 51 ]}

IC-PIC（情報相関と部分情報相関）に基づく方法は、DNA配列の基本相関特性を利用します。ICとPICは以下の式を用いて計算されます。

${\displaystyle IC_{\ell }=-2\sum _{i}P_{i}\log _{2}P_{i}+\sum _{ij}P_{ij}(\ell )\log _{2}P_{ij}(\ell )}$

${\displaystyle PIC_{ij}(\ell )=(P_{ij}(\ell )-P_{i}P_{j}(\ell ))^{2}}$

最終的なベクトルは次のようにして得られます。

${\displaystyle V={IC_{\ell } \over PIC_{ij}(\ell )}{\text{ where }}\ell \in \left\{\ell _{0},\ell _{0}+1,\ldots ,\ell _{0}+n\right\},}$

これは、ベース間の距離の範囲を定義する。^{[ 52 ]}

配列間のペアワイズ距離は、ユークリッド距離を用いて計算されます。このようにして得られた距離行列は、近隣結合法やUPGMA法などのクラスタリングアルゴリズムを用いて系統樹を構築するために使用できます。

例としては、コルモゴロフ複雑性の有効な近似値であるレンペル・ジブ複雑性などがある。一般に、圧縮ベースの手法は、シーケンス間の相互情報量を使用する。これは条件付きコルモゴロフ複雑性で表現され、つまり、他の文字列の事前知識が与えられた場合に文字列を生成するために必要な最短の自己限定プログラムの長さである。この尺度は、シーケンス内のkワードを測定することと関連があり、それらはシーケンスを生成するために容易に使用できる。これは、計算負荷の高い方法となる場合がある。コルモゴロフ複雑性アプローチの理論的基礎は、ベネット、ガクス、リー、ヴィタニ、ズレク (1998) が 情報距離を提案することによって築かれた。^{[ 53 ]}コルモゴロフ複雑性は計算不可能であるため、圧縮アルゴリズムによって近似された。圧縮が優れているほど、その方法は優れている。 Li、Badger、Chen、Kwong、Kearney、およびZhang（2001）は、このアプローチの最適ではないが正規化された形式を使用し、^{[ 54 ]} Li、Chen、Li、Ma、およびVitanyi（2003）による最適な正規化された形式は^{[ 55 ]に登場し、CilibrasiとVitanyi（2005）によって[ 56 ]}でより広範に証明されました。OtuとSayood（2003）は、Lempel-Ziv複雑性法 を使用して、系統樹構築のための5つの異なる距離尺度を構築しました。^{[ 57 ]}

複雑性のモデリングの文脈では、1 つ以上の統計モデルの次のシンボル予測が結合または競合して、過去に記録されたイベントに基づく予測が生成されます。各シンボル予測から得られるアルゴリズム情報コンテンツは、シーケンスの長さに比例する時間でアルゴリズム情報プロファイルを計算するために使用できます。このプロセスは、DNA 配列解析に適用されています。^{[ 58 ]}

反復マップを用いた配列解析は、1990年にHJ Jeffereyによって初めて導入されました^{[ 25 ]。}彼はゲノム配列を単位正方形にマッピングするためにカオスゲームを適用することを提案しました。このレポートでは、この手順をカオスゲーム表現（CGR）と名付けました。しかし、わずか3年後、このアプローチはN Goldmanによってマルコフ遷移表の投影として却下されました^{[ 59 ]} 。この反論は、その10年の終わりまでに、CGRがマルコフ遷移をフラクタルで順序フリー（次数フリー）表現に一対一でマッピングすることが判明し、覆されました^{[ 60 ]} 。反復マップが記号空間と数値空間の間の一対一マップを提供するという認識は、配列の比較と特徴付けのためのさまざまなアライメントフリーのアプローチの特定につながりました。これらの開発は、2013 年後半に JS Almeida によってレビューされました。^{[ 61 ]} https://github.com/usm/usm.github.com/wiki、^{[ 62 ]}のような多数の Web アプリケーションが利用可能で、クラウド コンピューティング用に開発された最新のMapReduce分散を最大限に活用する方法で任意の記号シーケンスをエンコードおよび比較する方法を示しています。