シーケンス比較のためのアルゴリズムの計算の複雑さ、ショートリードアセンブリ、およびゲノムアライメント

シーケンス比較、ショートリードアセンブリ、および全ゲノムアライメントのための多数のアルゴリズムが分子生物学の一般的なコンテキストで開発されました。高スループットシーケンスの技術開発、ゲノム生物学における多数のアプリケーション、および比較ゲノミクスに関する基本的な研究をサポートしています。これらのアルゴリズムの計算の複雑さは、元の研究論文で以前に報告されていますが、しばしばこの無視された財産は、体系的な方法で、より多くの聴衆のために以前にレビューされていません。キーシーケンス分析アルゴリズムの空間と時間の複雑さのレビューを提供し、アルゴリズムまたはデータ構造の最適化におけるさらなる研究の潜在的な機会を特定するために、包括的な方法でその特性を強調します。複雑さの側面は、細胞レベル以上の堅牢な生物学的シミュレーションが現実になると、予見可能な将来の前例のないスケールと複雑さに関するゲノムデータの継続的な増加に関連する課題に直面するため、極めて重要になる態勢が整っています。

A multitude of algorithms for sequence comparison, short-read assembly and whole-genome alignment have been developed in the general context of molecular biology, to support technology development for high-throughput sequencing, numerous applications in genome biology and fundamental research on comparative genomics. The computational complexity of these algorithms has been previously reported in original research papers, yet this often neglected property has not been reviewed previously in a systematic manner and for a wider audience. We provide a review of space and time complexity of key sequence analysis algorithms and highlight their properties in a comprehensive manner, in order to identify potential opportunities for further research in algorithm or data structure optimization. The complexity aspect is poised to become pivotal as we will be facing challenges related to the continuous increase of genomic data on unprecedented scales and complexity in the foreseeable future, when robust biological simulation at the cell level and above becomes a reality.