FASTSP: linear time calculation of alignment accuracy
FASTSP: linear time calculation of alignment accuracy
复制标题
DOI：
10.1093/bioinformatics/btr553
复制
发表时间：
2011-12-01
期刊：
影响因子：
5.8
通讯作者：
Warnow, Tandy
中科院分区：
文献类型：
--
作者：
Mirarab, Siavash;Warnow, Tandy
动机：多序列比对是许多生物学研究的基本组成部分，包括系统发育估计和蛋白质结构和功能预测。经常比较同一组未对齐序列上的不同比对，有时是为了评估比对方法的准确性或从一组估计的比对中推断出一致的比对。比较排列的三种标准技术Developer、Modeler和Total Column （TC）分数可以通过计算排列共享的同源性集来推导。然而，计算这个集合的蛮力技术在输入大小上是二次的。剩下的标准技术，克莱恩移位评分，本质上需要二次的时间。结果：在本文中，我们证明了这些分数中的每一个都可以在线性时间内计算，并且我们提出了FastSP，一个用于计算这些分数的线性时间算法。即使在我们探索的最大的比对中（一个有50,000个序列的比对），FastSP完成时间也不到2分钟，最多使用2 GB的主内存。最好的替代方法是qscore，当给定足够的内存（至少8 GB）时，该方法的经验运行时间与FastSP大致相同，但其渐近运行时间从未在理论上建立。此外，对于较低内存条件下（最多4 GB主内存）的大型对齐的比较，qscore使用大量内存（我们研究的数据集高达10 GB），花费更多时间并且无法分析最大的数据集。
Motivation: Multiple sequence alignment is a basic part of much biological research, including phylogeny estimation and protein structure and function prediction. Different alignments on the same set of unaligned sequences are often compared, sometimes in order to assess the accuracy of alignment methods or to infer a consensus alignment from a set of estimated alignments.Three of the standard techniques for comparing alignments, Developer, Modeler and Total Column (TC) scores can be derived through calculations of the set of homologies that the alignments share. However, the brute-force technique for calculating this set is quadratic in the input size. The remaining standard technique, Cline Shift Score, inherently requires quadratic time.Results: In this article, we prove that each of these scores can be computed in linear time, and we present FastSP, a linear-time algorithm for calculating these scores. Even on the largest alignments we explored (one with 50 000 sequences), FastSP completed < 2 min and used at most 2 GB of the main memory. The best alternative is qscore, a method whose empirical running time is approximately the same as FastSP when given sufficient memory (at least 8 GB), but whose asymptotic running time has never been theoretically established. In addition, for comparisons of large alignments under lower memory conditions (at most 4 GB of main memory), qscore uses substantial memory (up to 10 GB for the datasets we studied), took more time and failed to analyze the largest datasets.