title: 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.
authors.affiliation: 1 Department of Computer Science, University of Texas at Austin , Austin, Texas.
authors.forename: Siavash
authors.initials: S
authors.lastname: Mirarab
authors.forename: Nam
authors.initials: N
authors.lastname: Nguyen
authors.forename: Sheng
authors.initials: S
authors.lastname: Guo
authors.forename: Li-San
authors.initials: LS
authors.lastname: Wang
authors.forename: Junhyong
authors.initials: J
authors.lastname: Kim
authors.forename: Tandy
authors.initials: T
authors.lastname: Warnow
mesh_terms: D000465:Algorithms; D000595:Amino Acid Sequence; D001419:Bacteria / Q000145:classification / Q000235:genetics*; D001483:Base Sequence; D003198:Computer Simulation; D066264:Datasets as Topic; D019143:Evolution, Molecular; D056186:Metagenomics / Q000379:methods / Q000706:statistics & numerical data*; D008969:Molecular Sequence Data; D010802:Phylogeny; D010944:Plants / Q000145:classification / Q000235:genetics*; D016415:Sequence Alignment / Q000379:methods / Q000706:statistics & numerical data*; D012984:Software
keywords: algorithms; metagenomics; molecular evolution; multiple alignment; phylogenetic trees