pagan v20121025 (Multiple sequence alignment using partial-order graphs)
PAGAN is a general-purpose method for the alignment of sequence graphs. PAGAN is based on the phylogeny-aware progressive alignment algorithm and uses graphs to describe the uncertainty in the presence of characters at certain sequence positions. However, graphs also allow describing the uncertainty in input sequences and modeling (e.g., homopolymer errors in Roche 454 reads), or representing inferred ancestral sequences against which other sequences can then be aligned.
The development of PAGAN started in Nick Goldman's group at the EMBL-European Bioinfomatics Institute, UK, and continues now in Ari Löytynoja's group at the Institute of Biotechnology, University of Helsinki, Finland. PAGAN is still under development and will hopefully evolve to an easy-to-use, general-purpose method for phylogenetic sequence alignment.
As the graph representation has features that make PAGAN especially powerful for phylogenetic placement of sequences into existing alignments, the functionality necessary for that has been implemented first. The method and its uses for alignment extension are described in this paper and its supplementary material.