Combining partial order alignment and progressive multiple sequence alignment increases alignment speed and scalability to very large alignment problems. Export

@article{grasso:pogs, abstract = {MOTIVATION: Partial order alignment (POA) has been proposed as a new approach to multiple sequence alignment (MSA), which can be combined with existing methods such as progressive alignment. This is important for addressing problems both in the original version of POA (such as order sensitivity) and in standard progressive alignment programs (such as information loss in complex alignments, especially surrounding gap regions). RESULTS: We have developed a new Partial Order-Partial Order alignment algorithm that optimally aligns a pair of MSAs and which therefore can be applied directly to progressive alignment methods such as CLUSTAL. Using this algorithm, we show the combined Progressive POA alignment method yields results comparable with the best available MSA programs (CLUSTALW, DIALIGN2, T-COFFEE) but is far faster. For example, depending on the level of sequence similarity, aligning 1000 sequences, each 500 amino acids long, took 15 min (at 90\% average identity) to 44 min (at 30\% identity) on a standard PC. For large alignments, Progressive POA was 10-30 times faster than the fastest of the three previous methods (CLUSTALW). These data suggest that POA-based methods can scale to much larger alignment problems than possible for previous methods. AVAILABILITY: The POA source code is available at http://www.bioinformatics.ucla.edu/poa}, address = {Department of Chemistry and Biochemistry, Molecular Biology Institute, Center for Genomics and Proteomics, University of California, Los Angeles, CA 90095-1570, USA.}, author = {Grasso, C. and Lee, C.}, citeulike-article-id = {742103}, citeulike-linkout-0 = {http://dx.doi.org/10.1093/bioinformatics/bth126}, citeulike-linkout-1 = {http://bioinformatics.oxfordjournals.org/cgi/content/abstract/20/10/1546}, citeulike-linkout-2 = {http://view.ncbi.nlm.nih.gov/pubmed/14962922}, citeulike-linkout-3 = {http://www.hubmed.org/display.cgi?uids=14962922}, day = {10}, doi = {10.1093/bioinformatics/bth126}, issn = {1367-4803}, journal = {Bioinformatics}, keywords = {alignment, graph, partial\_order}, month = {July}, number = {10}, pages = {1546--1556}, posted-at = {2008-11-12 16:55:04}, priority = {2}, title = {Combining partial order alignment and progressive multiple sequence alignment increases alignment speed and scalability to very large alignment problems.}, url = {http://dx.doi.org/10.1093/bioinformatics/bth126}, volume = {20}, year = {2004} }

TY - JOUR ID - grasso:pogs L3 - citeulike-article-id:742103 N2 - MOTIVATION: Partial order alignment (POA) has been proposed as a new approach to multiple sequence alignment (MSA), which can be combined with existing methods such as progressive alignment. This is important for addressing problems both in the original version of POA (such as order sensitivity) and in standard progressive alignment programs (such as information loss in complex alignments, especially surrounding gap regions). RESULTS: We have developed a new Partial Order-Partial Order alignment algorithm that optimally aligns a pair of MSAs and which therefore can be applied directly to progressive alignment methods such as CLUSTAL. Using this algorithm, we show the combined Progressive POA alignment method yields results comparable with the best available MSA programs (CLUSTALW, DIALIGN2, T-COFFEE) but is far faster. For example, depending on the level of sequence similarity, aligning 1000 sequences, each 500 amino acids long, took 15 min (at 90% average identity) to 44 min (at 30% identity) on a standard PC. For large alignments, Progressive POA was 10-30 times faster than the fastest of the three previous methods (CLUSTALW). These data suggest that POA-based methods can scale to much larger alignment problems than possible for previous methods. AVAILABILITY: The POA source code is available at http://www.bioinformatics.ucla.edu/poa IS - 10 JF - Bioinformatics SN - 1367-4803 AD - Department of Chemistry and Biochemistry, Molecular Biology Institute, Center for Genomics and Proteomics, University of California, Los Angeles, CA 90095-1570, USA. EP - 1556 TI - Combining partial order alignment and progressive multiple sequence alignment increases alignment speed and scalability to very large alignment problems. VL - 20 SP - 1546 KW - alignment KW - graph KW - partial_order AU - Grasso, C AU - Lee, C PY - 2004/07/10/ UR - http://dx.doi.org/10.1093/bioinformatics/bth126 ER -