title: A greedy, graph-based algorithm for the alignment of multiple homologous gene lists.
abstract: BACKGROUND
  Many comparative genomics studies rely on the correct identification of homologous genomic regions using accurate alignment tools. In such case, the alphabet of the input sequences consists of complete genes, rather than nucleotides or amino acids. As optimal multiple sequence alignment is computationally impractical, a progressive alignment strategy is often employed. However, such an approach is susceptible to the propagation of alignment errors in early pairwise alignment steps, especially when dealing with strongly diverged genomic regions. In this article, we present a novel accurate and efficient greedy, graph-based algorithm for the alignment of multiple homologous genomic segments, represented as ordered gene lists.
  
  
  RESULTS
  Based on provable properties of the graph structure, several heuristics are developed to resolve local alignment conflicts that occur due to gene duplication and/or rearrangement events on the different genomic segments. The performance of the algorithm is assessed by comparing the alignment results of homologous genomic segments in Arabidopsis thaliana to those obtained by using both a progressive alignment method and an earlier graph-based implementation. Especially for datasets that contain strongly diverged segments, the proposed method achieves a substantially higher alignment accuracy, and proves to be sufficiently fast for large datasets including a few dozens of eukaryotic genomes.
  
  
  BACKGROUND
  http://bioinformatics.psb.ugent.be/software. The algorithm is implemented as a part of the i-ADHoRe 3.0 package.
authors.affiliation: Department of Information Technology, Ghent University, Ghent, Belgium.
authors.forename: Jan
authors.initials: J
authors.lastname: Fostier
authors.forename: Sebastian
authors.initials: S
authors.lastname: Proost
authors.forename: Bart
authors.initials: B
authors.lastname: Dhoedt
authors.forename: Yvan
authors.initials: Y
authors.lastname: Saeys
authors.forename: Piet
authors.initials: P
authors.lastname: Demeester
authors.forename: Yves
authors.initials: Y
authors.lastname: Van de Peer
authors.forename: Klaas
authors.initials: K
authors.lastname: Vandepoele
mesh_terms: D000465:Algorithms; D017360:Arabidopsis / Q000235:genetics; D019295:Computational Biology / Q000379:methods; D016678:Genome; D023281:Genomics / Q000379:methods*; D016415:Sequence Alignment / Q000379:methods*; D012984:Software