Gene Order Alignment on Trees with MultiOrthoAlign

Overview

Journal BMC Genomics

Publisher Biomed Central

Specialty Genetics

Date 2015 Jan 10

PMID 25572278

Citations 1

Authors

Billel Benzaid

Nadia El-Mabrouk

Affiliations

Soon will be listed here.

Abstract

We relate the comparison of gene orders to an alignment problem. Our evolutionary model accounts for both rearrangement and content-modifying events. We present a heuristic based on dynamic programming for the inference of the median of three genomes and apply it in a phylogenetic framework. multiOrthoAlign is shown accurate on simulated and real datasets, and shown to significantly improve the running-time of DupLoCut, an "almost" exact algorithm based on linear programming, developed recently for the same problem.

Citing Articles

Operon-based approach for the inference of rRNA and tRNA evolutionary histories in bacteria.

Pawliszak T, Chua M, Leung C, Tremblay-Savard O BMC Genomics. 2020; 21(Suppl 2):252.

PMID: 32299351 PMC: 7160887. DOI: 10.1186/s12864-020-6612-2.

References

Yang Z, Sankoff D . Natural parameter values for generalized gene adjacency. J Comput Biol. 2010; 17(9):1113-28. DOI: 10.1089/cmb.2010.0099. View

Darling A, Mau B, Perna N . progressiveMauve: multiple genome alignment with gene gain, loss and rearrangement. PLoS One. 2010; 5(6):e11147. PMC: 2892488. DOI: 10.1371/journal.pone.0011147. View

Bergeron A, Stoye J . On the similarity of sets of permutations and its applications to genome comparison. J Comput Biol. 2006; 13(7):1340-54. DOI: 10.1089/cmb.2006.13.1340. View

Tannier E, Zheng C, Sankoff D . Multichromosomal median and halving problems under different genomic distances. BMC Bioinformatics. 2009; 10:120. PMC: 2683817. DOI: 10.1186/1471-2105-10-120. View

Schwartz S, Kent W, Smit A, Zhang Z, Baertsch R, Hardison R . Human-mouse alignments with BLASTZ. Genome Res. 2003; 13(1):103-7. PMC: 430961. DOI: 10.1101/gr.809403. View

Delcher A, Kasif S, Fleischmann R, Peterson J, White O, Salzberg S . Alignment of whole genomes. Nucleic Acids Res. 1999; 27(11):2369-76. PMC: 148804. DOI: 10.1093/nar/27.11.2369. View

Tremblay-Savard O, Benzaid B, Lang B, El-Mabrouk N . Evolution of tRNA Repertoires in Bacillus Inferred with OrthoAlign. Mol Biol Evol. 2015; 32(6):1643-56. DOI: 10.1093/molbev/msv029. View

Elias I . Settling the intractability of multiple alignment. J Comput Biol. 2006; 13(7):1323-39. DOI: 10.1089/cmb.2006.13.1323. View

Durand D, Sankoff D . Tests for gene clustering. J Comput Biol. 2003; 10(3-4):453-82. DOI: 10.1089/10665270360688129. View

10.

Haas B, Delcher A, Wortman J, Salzberg S . DAGchainer: a tool for mining segmental genome duplications and synteny. Bioinformatics. 2004; 20(18):3643-6. DOI: 10.1093/bioinformatics/bth397. View

11.

Sankoff D, Cedergren R, Lapalme G . Frequency of insertion-deletion, transversion, and transition in the evolution of 5S ribosomal RNA. J Mol Evol. 1976; 7(2):133-49. DOI: 10.1007/BF01732471. View

12.

Holloway P, Swenson K, Ardell D, El-Mabrouk N . Ancestral genome organization: an alignment approach. J Comput Biol. 2013; 20(4):280-95. DOI: 10.1089/cmb.2012.0292. View

13.

El-Mabrouk N, Sankoff D . Analysis of gene order evolution beyond single-copy genes. Methods Mol Biol. 2012; 855:397-429. DOI: 10.1007/978-1-61779-582-4_15. View

14.

Brudno M, Do C, Cooper G, Kim M, Davydov E, Green E . LAGAN and Multi-LAGAN: efficient tools for large-scale multiple alignment of genomic DNA. Genome Res. 2003; 13(4):721-31. PMC: 430158. DOI: 10.1101/gr.926603. View

15.

Andreotti S, Reinert K, Canzar S . The duplication-loss small phylogeny problem: from cherries to trees. J Comput Biol. 2013; 20(9):643-59. PMC: 3761417. DOI: 10.1089/cmb.2013.0057. View