根から葉への回帰法による大規模多重配列アラインメント

多重配列アラインメント（multiple sequence alignment；MSA）は構造的、進化的予測に用いられているが、大規模データセットのアラインメントは複雑であるため、累進アルゴリズムなどの近似解法を用いる必要がある。累進的MSA法は、最も類似性の高い配列のアラインメントから出発し、その後で残りの配列を案内木に基づいて葉から根へと組み込んでいく。この方法の精度は、配列の数が大規模化するにつれて大きく低下する。本論文で紹介する回帰アルゴリズムは、標準的なワークステーションで最大140万個の配列のMSAを可能とし、配列数が1万個を超えるデータセットの精度を大幅に向上させるものである。この回帰アルゴリズムは累進アルゴリズムとは反対向きに働き、最も類似性の低い配列のアラインメントから出発する。また、効率的な分割統治法を用い、サードパーティーのアラインメント法を元の複雑さにかかわらず線形時間で実行する。この方法は、最近発表されたEarth BioGenome Project（真核生物150万種のゲノムを含む）のような極めて大規模なゲノムデータセットの解析を可能にすると考えられる。