Accurate extension of multiple sequence alignments using a phylogeny-aware graph algorithm

By Ari Löytynoja, Albert J. Vilella, Nick Goldman. 2012

140 citations recorded by the source corpus.

Motivation: Accurate alignment of large numbers of sequences is demanding and the computational burden is further increased by downstream analyses depending on these alignments. With the abundance of sequence data, an integrative approach of adding new sequences to existing alignments without their full re-computation and maintaining the relative matching of existing sequences is an attractive option. Another current challenge is the extension of reference alignments with fragmented sequences, as those coming from next-generation metagenomics, that contain relatively little information. Widely used methods for alignment extension are based on profile representation of reference sequences. These do not incorporate and use phylogenetic information and are affected by the composition of the reference alignment and the phylogenetic positions of query sequences. Results: We have developed a method for phylogeny-aware alignment of partial-order sequence graphs and apply it here to the extension of alignments with new data. Our new method, called PAGAN, infers ancestral sequences for the reference alignment and adds new sequences in their phylogenetic context, either to predefined positions or by finding the best placement for sequences of unknown origin. Unlike profile-based alternatives, PAGAN considers the phylogenetic relatedness of the sequences and is not affected by inclusion of more diverged sequences in the reference set. Our analyses show that PAGAN outperforms alternative methods for alignment extension and provides superior accuracy for both DNA and protein data, the improvement being especially large for fragmented sequences. Moreover, PAGAN-generated alignments of noisy next-generation sequencing (NGS) sequences are accurate enough for the use of RNA-seq data in evolutionary analyses. Availability: PAGAN is written in C++, licensed under the GPL and its source code is available at http://code.google.com/p/pagan-msa. Contact: ari.loytynoja@helsinki.fi Supplementary information: Supplementary data are available at Bioinformatics online.

Subfields: Genetics, Molecular Biology

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Genetics

In Molecular Biology

Citations in the corpus

MAFFT Multiple Sequence Alignment Software Version 7: Improvements in Performance and Usability (2013, methodology): “A limitation of the ––add option in MAFFT for this purpose was pointed out in Lo¨ytynoja et al. (2012).”
msa: an R package for multiple sequence alignment (2015, methodology): “T-Coffee (Notredame et al., 2000) and MUSCLE (Edgar, 2004a, b) are other methods that are widely used. ClustalOmega (Sievers et al., 2011) is a more recent top-notch method that has been designed to align large numbers of sequences in relatively short time. For a more comprehensive overview of multi”
The Harvest suite for rapid core-genome alignment and visualization of thousands of intraspecific microbial genomes (2014, methodology): “With well-defined reference cores, outbreaks could be accurately typed in real-time by mapping sequences directly to the tree using phylogenetically aware methods such as pplacer [105] or PAGAN [106].”
PhyloSift: phylogenetic analysis of genomes and metagenomes (2014, methodology): “Applica238 tion of a profile-HMM to align highly divergent sequences suffers some documented shortcomings, in 239 particular that alignment accuracy decreases with divergence of source sequences used to construct the 240 profile-HMM [34].”