配列比較は、分子配列間の関係を研究するために広く使用されている。配列比較のための主なツールは、global（ref.1）およびlocal（ref.2）シーケンスアラインメントを含むアラインメントベースの方法である。 BLAST（ref.3）のようなアラインメントベースのツールおよびRefSeq（ref.4）のようなシーケンスデータベースの出現により、アラインメントベースの方法は広範囲の用途で広く使用されている。それらの広範な用途にもかかわらず、位置合わせに基づく方法はいくつかの状況において適切ではない。第一に、遺伝子調節領域は一般に高度に保存されておらず、アラインメントに基づくアプローチは類似の転写因子によって結合されている関連調節領域を同定することを困難にする（ref.5）。第二に、次世代シーケンシング（NGS）技術は大量のショートリードを生成するため、ゲノム研究とメタゲノム研究の両方にそれらを組み合わせることは困難である。多くのサンプルにわたって長くアセンブリされたコンティグがなければ、ゲノムとメタゲノムを比較するためのアラインメントベースの方法では困難である（ref.6,7）。第三に、ウイルスは同じようなワードパターンの用法を持つ細菌宿主に感染する可能性が高く（ref.8、9）、したがって、ウイルスの宿主はそれらのワードパターンの用法に基づいて推定される可能性がある。しかしながら、アラインメントに基づく方法は、通常、ウイルス - 宿主感染性関連性の研究には適用できない。
アラインメントフリーのシーケンス比較法は、アラインメントに基づく方法が適切でないかまたは実際に実施するには時間がかかりすぎる場合に、配列間の関係を研究するための魅力的な代替法である（ref.10、11）。Briefing in Bioinformaticsの特別号で最近レビューされた（ref.12）、k-mer、最長共通部分列、最短欠如パターンなどに基づくものを含む、いくつかのタイプのアラインメントフリーアプローチが利用可能である。ここでは、k-mer数を使用したアライメントフリー統計に焦点を当てる。これらの手法は各シーケンスを k-mer（または同等に k-tuple、k-gram）カウント特徴空間に射影し、ここでシーケンス情報はk-mer頻度などの数値に変換される。追加の計算上の複雑さがある spaced k-mers を使用する相違測定は考慮しない。（一部略）
CAFEは、CVTree（ref.15）、d2（ref.13）、d2S（ref.13）など、バックグラウンド調整されたk-merカウントに基づく最近開発されたメジャーの計算を大幅にスピードアップし、同時にメモリ使用量を削減する。さらに、CAFEは、Chebyshev（Ch）、Euclidean（Eu）、Manhattan（Ma）、d2 dissimilarity（ref.16）、Jensen-Shannon divergence（JS）（ref.17）、feature frequency profiles (FFP)（ref.18）、そしてCo-phylog（ref.19）などのk-merカウントに基づく10の従来の尺度を統合する。 CAFEはまた、JaccardやHammingのdistanceなど、k-merの有無に基づいて15の基準を提供する。さらに、霊長類、脊椎動物、微生物のゲノム配列からメタゲノムシーケンシングリードにに至るまで、実際のデータセットでCAFEを使用したアライメントフリーの非類似度測定の価値を示す。
CAFEは、NGS技術からアセンブリされたゲノム配列とアセンブリされていないショットガンシーケンシングの両方のシーケンスデータを扱い、高速でメモリ効率の良いk-merカウントツールであるJELLYFISH（ref.20）によってk-merをカウントする。 JELLYFISHは、クエリシーケンスを並列に与えられたすべてのk-merカウントを含む圧縮データベースを生成する。その後、CAFEはデータベースをロードし、さまざまな非類似度に関して必要な変換情報を生成する。例えば、ｋ-merの存在／不在に基づく尺度は、ｋ-merカウントを存在／不在指標に二値化する。ほとんどの従来の尺度は、k-merカウントをｋ-merスペクトラムに正規化する。その上、予想されるｋ -merカウントは、CVTree、d2およびD2Sのようなバックグラウンド調整されたｋ-merカウントに基づく最近開発された尺度に関与している。そのような場合、配列のマルコフモデルは、それに応じて配列データから推定されるパラメータを用いて、基礎となる生成モデルとして想定される。マルコフ次数は、手動で設定することも、ベイズ情報量基準（BIC）を使用して自動的に選択することもできる（ref.21）。
結果として得られるシーケンス間のペアワイズの非類似性は、対称行列を形成する。 CAFEは、非類似度行列を標準のPHYLIP形式で直接出力できる。あるいは、CAFEは、UPGMAアルゴリズムを使用して配列を樹状図にクラスター化すること、マトリックスのヒートマップ可視化、マトリックスtを射影することを含む、4種類の組み込み下流可視化分析を提供する。
インストール
本体 Github
Githubにあるリンクからダウンロードする。mac版とwindows版が用意されている。
使い方
解凍して、中にあるCAFEGUIをダブルクリックして起動。
またはターミナルから叩いて起動。
左上の一番左にあるLoadボタンをクリック
ここではテストデータの Phylip formatファイルを選択。
Dendrogram
右上のボタンから拡大縮小と図のダウンロードができる（.PNG）。
タブを切り替えることで視覚化方法を比較方法と視覚化方法を切り替えできる
principal coordinate analysis (PCoA)
Heatmap
Network
FASTAファイルを読み込んで実行するには、FASTAファイル( .faか .fna)のディレクトリを指定する。左から３番目のAdd all genomeを選択。
ディレクトリを指定
またはFASTAファイルを個別に読み込む。左から２番目のAdd one genomeを選択。
読み込まれたファイルが表示される。
全てのFASTAを読み込んだら、パラメータを決める。
defaultではマンハッタン距離（Ma）、k-mer=8、k-mer配列の逆相補鎖は考慮しない。
右上のRunボタンを押して比較を実行
計算が終わると結果が表示される。
Start parsing the arguments...
CAFE: aCcelerated Alignment-FrEe sequence analysis
Description: The program provides 29 alignment-free sequence distance measures.
Authors: Yang Lu and Prof. Fengzhu Sun, Computational and Molecular Biology, University of Southern California.
usage:
./cafe [options]* -D <dist> -I <fa_files> -K <intK>
Main arguments
-D <dist> Comma-separated list of distance measurements, E.g. -D D2star,Ma,CVtree. The options include:
Conventional measures based on k-mer counts :
Ch: Chebyshev distance
Canberra: Canberra distance
Chisq: Chi-Square distance
Co-phylog: Co-phylog distance with the seed C_{(k-1)/2,(k-1)/2}O_{1} when k is odd or C_{k/2-1,k/2}O_{1} when k is even
D2: D2 distance
Eu: Euclidean distance
FFP: Feature frequency profiles (FFP)
JS: Jensen-Shannon divergence
Ma: Manhattan distance
Pearson: Pearson distance
Newly developed measures based on background adjusted k-mer counts:
CVtree: CVtree distance
D2shepp: D2shepp distance
D2star: D2star distance
Measures based on presence/absence of k-mers:
Anderberg: Anderberg distance
Antidice: anti-Dice distance
Dice: Dice distance
Gower: Gower distance
Hamman: Hamman distance
Hamming: Hamming distance
Jaccard: Jaccard distance
Kulczynski: Kulczynski distance
Matching: Matching distance
Ochiai: Ochiai distance
Phi: Pearson Phi distance
Russel: Russel-Rao distance
Sneath: Sneath-Sokal distance
Tanimoto: Rogers-Tanimoto distance
Yule: Yule distance
-I <fa_files> Comma-separated list of sequence fasta files, e.g. -I speciesA.fa,speciesB.fa,speciesC.fa. Pairwise similarity is calculated based upon the sequences specified with this option.
-K <intK> Kmer Length
Options
-J <jfexe_path> Use jellyfish to accelerate kmer counting. <jfexe_path> denotes the file path of jellyfish executable file, e.g. jellyfish-2.2.4/bin/./jellyfish
-L <lower> Only consider k-mer with occurrence >= <lower>. The default value is 0.
-M <order> Markov Order involved in D2star and D2shepp. There are two possible options. The first option is one single value indicating that all the sequences use the same order. The second option is comma-separated list of orders. Notice that the length of the list should match the number of fasta files. The order value could be non-negative integer but less than Kmer length or "-1" with the special intention to automatically infer the suitable order (not suitable for JS). The default Markov Order is -1 (Automaticcaly determine by BIC).
-R Consider Reverse Complement in kmer counting.
-S <dir> Save/Load calculated k-mer count binary files to the folder <dir>. Each input fasta file corresponds to particular model.
-O <path> Output results to file at <path>
-T <type> The output type as the input to downstream analysis, including: plain, phylip (as hierarchical clustering), cytoscape (as network analysis) and mds (Multidimensional Scaling as 2D plotting). E.g. -T mds. The default type is plain.
Examples:
./cafe -M 0 -O output_path -S model_dir -T plain -I speciesA.fa,speciesB.fa -J jellyfish-2.2.4/bin/./jellyfish -K 10 -D D2star,Ma
./cafe -M 0 -S model_dir -I speciesA.fa,speciesB.fa -J jellyfish-2.2.4/bin/./jellyfish -K 10 -D D2star,Ma
./cafe -M 0 -L 2 -I speciesA.fa,speciesB.fa -J jellyfish-2.2.4/bin/./jellyfish -K 10 -D D2star,Ma -R
引用
CAFE: aCcelerated Alignment-FrEe sequence analysis
Yang Young Lu, Kujin Tang, Jie Ren, Jed A. Fuhrman, Michael S. Waterman, Fengzhu Sun
Nucleic Acids Res. 2017 Jul 3; 45(Web Server issue): W554–W559
