次世代シークエンシング時代では、増え続ける生物学的配列やそのバリエーションを正確にアノテーションするための信頼性の高い、高速かつ効率的なアプローチが求められている。類似性検索に基づくアノテーションのtransferは、標準的なアプローチである。全タンパク質比較の手順は、データベースに既に存在する情報に基づいて配列をアノテーションする様々な利用可能な方法の前段階である。また、その際には、配列比較の時間を短縮するために、データの前処理を行う方法が必要となる。
大量の配列（データベース全体）を、限られた最小値と期待されるアラインメントカバレッジに応じて配列長値（残基数）を制約した集合に分割し、最適化するアルゴリズムを提案する。タンパク質配列をその長さに応じて最適にグループ化し、選択された長さの範囲内にある配列間のall-against-allシーケンスアラインメントを計算するという考え方である。この論文では、数学的に最適な解を記述し、本手法が実世界のケースで5倍のスピードアップにつながることを示す。本手法の実装は http://www.biocomp.unibo.it/∼giuseppe/partitioning.html からダウンロードできる。
タンパク質データセットにおける「all-against-all」のシーケンスアラインメントは、BLAST（Altschul etal. 1990）や動的プログラミングアプローチ（Needleman and Wunschun, 1970）などのプログラムを用いて日常的に行われている。これにより、配列は配列同一性値のサブセットにグループ化され、タンパク質配列間の構造的特徴や機能的特徴の伝達など、いくつかのアプリケーションで重要となる。少なくとも約30％の配列同一性を共有するタンパク質は、その三次元構造が重複している可能性があり（Chothia and Lesk, 1986）、少なくとも約60％の配列同一性を共有するタンパク質は、同様の機能を共有している可能性が高い（Rost, 2002; Tian and Skolnick, 2003）。また、アノテーションをtransferする前に、ペアワイズアラインメントされた配列の相対的な長さを考慮することも重要である(Devos and Valencia, 2001)。マルチドメイン蛋白質はシングルドメイン蛋白質よりも機能的に保存されていないため（Hegyi and Gerstein, 2001）、相同性検索後の機能transferに基づく方法では、機能の異なる蛋白質を同じクラスタ内でグループ化することがあり得る。したがって、アノテーション方法の開発では、配列同一性の値とアライメント長（カバレッジ）についてのオーバーラップの割合の両方が制約に含まれた（Mieleら、2011; Piovesanら、2011、2013）。進化論的研究は、そのワークフローの初期段階でのアラインメントを含む（Vilella etal. 2009; Waterhouse etal. 2013）が、同時に計算を高速化するための計算方法も重要になる（Roth etal. 2008; Sonnhammer etal. 2014; Wittwer etal. 2014）。
計算コストを考えると、 all-against-all similarity searchは非常に負荷の高いプロセスである。最近、進化研究に関連する問題において、Wittwer etal. (2014)は、部分配列レベルの相同性を考慮することで、相同配列を検索する可能性を維持したまま、 all-against-all similarity searchの処理速度を4倍に高速化できることを示した。本研究では、期待されるアラインメントカバレッジを制限することにより、 similarity searchの計算時間を高速化するアルゴリズムを提案する。
HP（AlignBucketのソースコードに加えて、論文で使用されたデータセットもダウンロード可能）
http://www.biocomp.unibo.it/~giuseppe/partitioning.html
インストール
ビルド依存
The program was tested on a GNU/Linux Debian 7 system.
The required libraries are:
git clone https://github.com/profgiuseppe/alignbucket.git
cd alignbucket/
make
chmod u+x alignbucket
> ./alignbucket
# ./alignbucket
Using default minimum length: 1
ERROR: please specify a distribution or a fasta file
Allowed options:
--help produce help message
--delta arg (=90) Coverage percentage needed, please see the paper
-s [ --start ] arg Minimum sequence length to consider
-d [ --distribution ] arg file with length distribution. The content should
be <length> <num. of sequences>
-f [ --fasta ] arg file containing the sequences in FASTA format
--outdir arg output directory
-v [ --verbose ] verbose mode. WARNING: may generate a huge amount
of data
> ./alignbucket.sh -h
# ./alignbucket.sh -h
Using default minimum length: 1
Reading fasta file -h
ERROR: Can't open file -h
実行方法
ランにはalignbucket.shを使う。FASTAファイルを指定する。論文では2015年5月のuniprot_sprotを使用している。
alignbucket.sh fasta_file --delta 90
デフォルトではFASTAファイルを最適化されたバケットに分割して、90%のカバレッジを実現する。xxx-yyy.fastaという形式で出力されるが、xxxとyyyはファイル内の配列の最小長と最大長を表している。
出力
アラインメントカバレッジが同程度のチャンクに分割される。
uniprot_sprot_2015の分割結果の1-4を開いてみた。
（なぜこうゆう配列が登録されているのかは分からない）
引用
AlignBucket: a tool to speed up ‘all-against-all’ protein sequence alignments optimizing length constraints
Giuseppe Profiti, Piero Fariselli, Rita Casadio
Bioinformatics, Volume 31, Issue 23, 1 December 2015, Pages 3841–3843,
関連
