title: Multiple sequence alignment using partial order graphs.
abstract: BACKGROUND
  Progressive Multiple Sequence Alignment (MSA) methods depend on reducing an MSA to a linear profile for each alignment step. However, this leads to loss of information needed for accurate alignment, and gap scoring artifacts.
  
  
  RESULTS
  We present a graph representation of an MSA that can itself be aligned directly by pairwise dynamic programming, eliminating the need to reduce the MSA to a profile. This enables our algorithm (Partial Order Alignment (POA)) to guarantee that the optimal alignment of each new sequence versus each sequence in the MSA will be considered. Moreover, this algorithm introduces a new edit operator, homologous recombination, important for multidomain sequences. The algorithm has improved speed (linear time complexity) over existing MSA algorithms, enabling construction of massive and complex alignments (e.g. an alignment of 5000 sequences in 4 h on a Pentium II). We demonstrate the utility of this algorithm on a family of multidomain SH2 proteins, and on EST assemblies containing alternative splicing and polymorphism.
  
  
  BACKGROUND
  The partial order alignment program POA is available at http://www.bioinformatics.ucla.edu/poa.
authors.affiliation: Department of Chemistry and Biochemistry, University of California, Los Angeles, Los Angeles, CA 90095-1570, USA. leec@mbi.ucla.edu
authors.forename: Christopher
authors.initials: C
authors.lastname: Lee
authors.forename: Catherine
authors.initials: C
authors.lastname: Grasso
authors.forename: Mark F
authors.initials: MF
authors.lastname: Sharlow
mesh_terms: D000465:Algorithms; D001483:Base Sequence; D004247:DNA / Q000235:genetics*; D030541:Databases, Genetic; D020224:Expressed Sequence Tags; D051599:Glucose-1-Phosphate Adenylyltransferase; D006801:Humans; D015233:Models, Statistical; D008969:Molecular Sequence Data; D009713:Nucleotidyltransferases; D010940:Plant Proteins / Q000235:genetics; D011786:Quality Control; D012333:RNA, Messenger / Q000235:genetics; D012680:Sensitivity and Specificity; D016415:Sequence Alignment / Q000379:methods*; D017385:Sequence Homology; D012984:Software; D013997:Time Factors
chemical_list: D010940:Plant Proteins; D012333:RNA, Messenger; C111076:Sh2 protein, plant; D004247:DNA; D009713:Nucleotidyltransferases; D051599:Glucose-1-Phosphate Adenylyltransferase