PASTA: Ultra-Large Multiple Sequence Alignment for Nucleotide and Amino-Acid Sequences

Abstract

We introduce PASTA, a new multiple sequence alignment algorithm. PASTA uses a new technique to produce an alignment given a guide tree that enables it to be both highly scalable and very accurate. We present a study on biological and simulated data with up to 200,000 sequences, showing that PASTA produces highly accurate alignments, improving on the accuracy and scalability of the leading alignment methods (including SATé). We also show that trees estimated on PASTA alignments are highly accurate--slightly better than SATé trees, but with substantial improvements relative to other methods. Finally, PASTA is faster than SATé, highly parallelizable, and requires relatively little memory.

Keywords

ScalabilityMultiple sequence alignmentParallelizable manifoldComputer scienceSequence (biology)Alignment-free sequence analysisSequence alignmentTree (set theory)AlgorithmComputational biologyData miningBiologyMathematicsPeptide sequenceGenetics

Affiliated Institutions

Related Publications

PANDIT: an evolution-centric database of protein and associated nucleotide domains with inferred trees

Simon Whelan

PANDIT is a database of homologous sequence alignments accompanied by estimates of their corresponding phylogenetic trees. It provides a valuable resource to those studying phyl...

2005 Nucleic Acids Research 70 citations

Recent Evolutions of Multiple Sequence Alignment Algorithms

Cédric Notredame

An ever-increasing number of biological modeling methods depend on the assembly of an accurate multiple sequence alignment (MSA). These include phylogenetic trees, profiles, and...

2007 PLoS Computational Biology 219 citations

The order of sequence alignment can bias the selection of tree topology.

James A. Lake

Sequential pairwise alignment of multiple sequences is a widely used procedure (Kruskal 1983 ).It is useful and generally successful when sequences within a set differ by relati...

1991 Molecular Biology and Evolution 150 citations

MUSCLE: multiple sequence alignment with high accuracy and high throughput

R. C. Edgar

We describe MUSCLE, a new computer program for creating multiple alignments of protein sequences. Elements of the algorithm include fast distance estimation using kmer counting,...

2004 Nucleic Acids Research 44728 citations

Generating consensus sequences from partialorder multiple sequence alignment graphs

Christopher J. Lee

Abstract Motivation: Consensus sequence generation is important in many kinds of sequence analysis ranging from sequence assembly to profile-based iterative search methods. Howe...

2003 Bioinformatics 99 citations

Publication Info

Year: 2014
Type: article
Volume: 22
Issue: 5
Pages: 377-386
Citations: 446
Access: Closed

External Links

View on DOI.org

Social Impact

Altmetric

PASTA: Ultra-Large Multiple Sequence Alignment for Nucleotide and Amino-Acid Sequences

PlumX Metrics

Social media, news, blog, policy document mentions

Citation Metrics

446

OpenAlex

Cite This

APA Style

                            
                                
                                    Siavash Mirarab, 
                                
                                    Nam Nguyen, 
                                
                                    Sheng Guo
                                
                                et al.
                            
                            (2014). 
                            PASTA: Ultra-Large Multiple Sequence Alignment for Nucleotide and Amino-Acid Sequences. 
                            Journal of Computational Biology
                            , 22
                            (5)
                            , 377-386.
                            https://doi.org/10.1089/cmb.2014.0156
                        

Identifiers

DOI: 10.1089/cmb.2014.0156