FASTSP: linear time calculation of alignment accuracy
Open Access
- 7 October 2011
- journal article
- research article
- Published by Oxford University Press (OUP) in Bioinformatics
- Vol. 27 (23) , 3250-3258
Abstract
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 Availability: The open-source software and executables are available online at http://www.cs.utexas.edu/~phylo/software/fastsp/. Contact:tandy@cs.utexas.eduKeywords
This publication has 29 references indexed in Scilit:
- PSAR: measuring multiple sequence alignment reliability by probabilistic samplingNucleic Acids Research, 2011
- Issues in bioinformatics benchmarking: the case study of multiple sequence alignmentNucleic Acids Research, 2010
- Upcoming challenges for multiple sequence alignment methods in the high-throughput eraBioinformatics, 2009
- Recent developments in the MAFFT multiple sequence alignment programBriefings in Bioinformatics, 2008
- Alignment Uncertainty and Genomic AnalysisScience, 2008
- Predicting and improving the protein sequence alignment quality by support vector regressionBMC Bioinformatics, 2007
- The M-Coffee web server: a meta-method for computing multiple sequence alignments by combining alternative alignment methodsNucleic Acids Research, 2007
- Greengenes, a Chimera-Checked 16S rRNA Gene Database and Workbench Compatible with ARBApplied and Environmental Microbiology, 2006
- MUSCLE: multiple sequence alignment with high accuracy and high throughputNucleic Acids Research, 2004
- CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choiceNucleic Acids Research, 1994