GramAlign: Fast alignment driven by grammar-based phylogeny

Multiple sequence alignment involves identifying related subsequences among biological sequences. When matches are found, the associated pieces are shifted so that when sequences are presented as successive rows—one sequence per row—homologous residues line-up in columns. Exact alignment of more than a few sequences is known to be computationally prohibitive. Thus many heuristic algorithms have been developed to produce good alignments in an efficient amount of time by determining an order by which pairs of sequences are progressively aligned and merged. GramAlign is such a progressive alignment algorithm that uses a grammar-based relative complexity distance metric to determine the alignment order. This technique allows for a computationally efficient and scalable program useful for aligning both large numbers of sequences and sets of long sequences quickly. The GramAlign software is available at http://bioinfo.unl.edu/gramalign.php for both source code download and a web-based alignment server.