PASTA: Ultra-large multiple sequence alignment for nucleotide and amino-acid sequences

Siavash Mirarab, Nam Nguyen, Sheng Guo, Li San Wang, Junhyong Kim, Tandy Warnow

Research output: Contribution to journalArticle

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.

Original languageEnglish (US)
Pages (from-to)377-386
Number of pages10
JournalJournal of Computational Biology
Volume22
Issue number5
DOIs
StatePublished - May 1 2015

Fingerprint

Multiple Sequence Alignment
Sequence Alignment
Amino Acid Sequence
Nucleotides
Amino acids
Alignment
Scalability
Data storage equipment

Keywords

  • algorithms
  • metagenomics
  • molecular evolution
  • multiple alignment
  • phylogenetic trees

ASJC Scopus subject areas

  • Modeling and Simulation
  • Molecular Biology
  • Genetics
  • Computational Mathematics
  • Computational Theory and Mathematics

Cite this

PASTA : Ultra-large multiple sequence alignment for nucleotide and amino-acid sequences. / Mirarab, Siavash; Nguyen, Nam; Guo, Sheng; Wang, Li San; Kim, Junhyong; Warnow, Tandy.

In: Journal of Computational Biology, Vol. 22, No. 5, 01.05.2015, p. 377-386.

Research output: Contribution to journalArticle

Mirarab, Siavash ; Nguyen, Nam ; Guo, Sheng ; Wang, Li San ; Kim, Junhyong ; Warnow, Tandy. / PASTA : Ultra-large multiple sequence alignment for nucleotide and amino-acid sequences. In: Journal of Computational Biology. 2015 ; Vol. 22, No. 5. pp. 377-386.
@article{c71945971a2143b5af283ca44c08d3c5,
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{\'e}). We also show that trees estimated on PASTA alignments are highly accurate - slightly better than SAT{\'e} trees, but with substantial improvements relative to other methods. Finally, PASTA is faster than SAT{\'e}, highly parallelizable, and requires relatively little memory.",
keywords = "algorithms, metagenomics, molecular evolution, multiple alignment, phylogenetic trees",
author = "Siavash Mirarab and Nam Nguyen and Sheng Guo and Wang, {Li San} and Junhyong Kim and Tandy Warnow",
year = "2015",
month = "5",
day = "1",
doi = "10.1089/cmb.2014.0156",
language = "English (US)",
volume = "22",
pages = "377--386",
journal = "Journal of Computational Biology",
issn = "1066-5277",
publisher = "Mary Ann Liebert Inc.",
number = "5",

}

TY - JOUR

T1 - PASTA

T2 - Ultra-large multiple sequence alignment for nucleotide and amino-acid sequences

AU - Mirarab, Siavash

AU - Nguyen, Nam

AU - Guo, Sheng

AU - Wang, Li San

AU - Kim, Junhyong

AU - Warnow, Tandy

PY - 2015/5/1

Y1 - 2015/5/1

N2 - 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.

AB - 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.

KW - algorithms

KW - metagenomics

KW - molecular evolution

KW - multiple alignment

KW - phylogenetic trees

UR - http://www.scopus.com/inward/record.url?scp=84926338043&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84926338043&partnerID=8YFLogxK

U2 - 10.1089/cmb.2014.0156

DO - 10.1089/cmb.2014.0156

M3 - Article

C2 - 25549288

AN - SCOPUS:84926338043

VL - 22

SP - 377

EP - 386

JO - Journal of Computational Biology

JF - Journal of Computational Biology

SN - 1066-5277

IS - 5

ER -