すべてのシーケンシング技術はある程度の不正確さを持っている。例えば、Illuminaプラットフォーム（Margulies et al、2005）は、 主に置換からなる1〜2％のエラー率を有し（Dohm et al、2008; Nakamura et al、2011）、PacBioプラットフォームは挿入および欠失からなる15％のエラー率を有する（Eid et al、2009）。このような技術の莫大なスループットにより、最近、効率的なエラー訂正アルゴリズムを開発するニーズが生み出されている。
シーケンシングエラーは、リードをリファレンスゲノムと比較することによって発見することができる。しかしながら、そのようなリファレンスは常に利用可能であるとは限らない。シーケンスがランダムであるか、または未知のソースから取得された場合、クラスタリングはエラーを修正するための主な戦略になる。たとえば、ランダムバーコードを使用して細胞や転写産物を追跡すると、この状況が発生する（Akhtar et al、2013; Schepers et al、2008）。シーケンシングエラーにより、削除する必要のある誤った（存在しない）バーコードが作成される。
シーケンスクラスタリングは、ノードがシーケンスを表し、エッジが関連するシーケンス間のマッチングを表すグラフ上のコミュニティ検出問題として見ることができる。このプロセスは、グラフが構築されるマッチングフェーズ（最も計算量が多い）と、コミュニティが識別されるクラスタリングフェーズで構成される。
ここでは、典型的に星形を有するランダムなバーコードをクラスタリングする「Starcode」と呼ばれるシーケンスクラスタリングアルゴリズムを説明する。Starcodeは全ペア検索に基づいており、すなわち、与えられたレーベンシュタイン距離 (wiki) 以下のシーケンスのすべてのペアがグラフ構築フェーズ中に識別される。マッチングはロスレスフィルタリングによって実行され、続いてprefix trieの枝を網羅的に検索する。アルゴリズムの新規性はポケット戦略であり、アルファベット順ソートシーケンスの冗長性を利用して不必要な再計算や速度を回避する。
本論文では、Starcodeを提示し、ベンチマークする。実際の生物学的データセットでは、Starcodeは既存のシーケンスクラスタリングソフトウェアよりも数倍高速だった。Starcodeはエラー訂正用に設計されているが、他の問題にも使用できることを示している。一例として、バクテリアゲノムおよびタンパク質-RNA相互作用実験におけるenriched motifsを同定するためにStarcodeを使用する。
インストール
ubuntu18.04でテストした。
git clone https://github.com/gui11aume/starcode
cd starcode/
make
> ./starcode
$ ./starcode
Usage: starcode [options]
general options:
-d --dist: maximum Levenshtein distance (default auto)
-t --threads: number of concurrent threads (default 1)
-q --quiet: quiet output (default verbose)
-v --version: display version and exit
cluster options: (default algorithm: message passing)
-r --cluster-ratio: min size ratio for merging clusters in
message passing (default 5.0)
-s --sphere: use sphere clustering algorithm
-c --connected-comp: cluster connected components
input/output options (single file, default)
-i --input: input file (default stdin)
-o --output: output file (default stdout)
input options (paired-end fastq files)
-1 --input1: input file 1
-2 --input2: input file 2
output options (paired-end fastq files, --non-redundant only)
--output1: output file1 (default input1-starcode.fastq)
--output2: output file2 (default input2-starcode.fastq)
output format options
--non-redundant: remove redundant sequences from input file(s)
--print-clusters: outputs cluster compositions
--seq-id: print sequence id numbers (1-based)
実行方法
許容する レーベンシュタイン距離の最大値を指定して実行する。指定しない場合、2 + "2 + [median seq length]/30"で計算される。最大値は8。
starcode -i input.fq -d 3 -t 12 -o output
- -i input file (default stdin)
- -o output file (default stdout)
-
-d maximum Levenshtein distance (default auto)
-
-t number of concurrent threads (default 1)
ペアエンドfastq
starcode -1 pair1.fq -2 pair2.fq -d auto -t 12 --output1 out1 --output2 out2
-
-1 input file 1
-
-2 input file 2
-
--output1 output file1 (default input1-starcode.fastq)
-
--output2 output file2 (default input2-starcode.fastq)
非冗長な配列を出力する。
starcode -i input.fq -d auto -t 12 --non-redundant -o output
- --non-redundant Removes redundant sequences from the output. Only the canonical sequence of each cluster is returned.
fastqライクなフォーマットで出力される（４行目のクオリティがIDの一部に置き換わっている）。
他の出力フォーマット
-
--print-clusters Adds a third column to the starcode output, containing the sequences that compose each cluster.
-
--seq-id Shows the input sequence order (1-based) of the cluster components.
出力フォーマットについてはGIthubのREADMEを参照してください。
引用
Starcode: sequence clustering based on all-pairs search
Eduard Zorita, Pol Cuscó, Guillaume J. Filion
Bioinformatics. 2015 Jun 15; 31(12): 1913–1919
