Swarming along the evolutionary branches sheds light on genome rearrangement scenarios

ABSTRACT

A genome rearrangement scenario describes a series of chromosome fusion, fission, and translocation operations that suffice to rewrite one genome into another. Exact algorithmic methods for this important problem focus on providing one solution, while the set of distance-wise equivalent scenarios is very large. Moreover, no criteria for filtering for biologically plausible scenarios is currently proposed. We present an original metaheuristic method that uses Ant Colony Optimization to randomly explore the space of optimal and suboptimal rearrangement scenarios. It improves on the state of the art both by permitting large-scale enumeration of optimal scenarios, and by labeling each with metrics that can be used for post-processing filtering based on biological constraints.

REFERENCES

• 1: D. A. Bader, B. Moret, and M. Yan. A linear-time algorithm for computing inversion distances between signed permutations with an experimental study. Journal of Computational Biology, 8(5):483--491, 2001.
• 2: Severine Berard , Anne Bergeron , Cedric Chauve , Christophe Paul, Perfect Sorting by Reversals Is Not Always Difficult, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.4 n.1, p.4-16, January 2007 [doi>10.1109/TCBB.2007.1011]
• 3: A. Bergeron, C. Chauve, T. Hartman, and K. Saint-Onge. On the properties of sequences of reversals that sort a signed permutation. In Proceedings of JOBIM 2002, pages 99--108, 2002.
• 4: Marília D. V. Braga , Marie-France Sagot , Celine Scornavacca , Eric Tannier, Exploring the Solution Space of Sorting by Reversals, with Experiments and an Application to Evolution, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.5 n.3, p.348-356, July 2008 [doi>10.1109/TCBB.2008.16]
• 5: A. Darling, I. Mikls, and M. Ragan. Dynamics of genome rearrangement in bacterial populations. PLoS Genetics, 4(7):e1000128 doi:10.1371/journal.pgen.1000128, 2008.
• 6: T. Dobzhansky and A. H. Sturtevant Inversions in the chromosomes of drosophila pseudoobscura, Genetics, 23(1):28--64, 1938.
• 7: Marco Dorigo , Thomas Stützle, Ant Colony Optimization, Bradford Book, 2004
• 8: Kathryn A. Dowsland , Jonathan M. Thompson, An improved ant colony optimisation heuristic for graph colouring, Discrete Applied Mathematics, v.156 n.3, p.313-324, February, 2008 [doi>10.1016/j.dam.2007.03.025]
• 9: Adrien Goeffon , Macha Nikolski , David J. Sherman, An efficient probabilistic population-based descent for the median genome problem, Proceedings of the 10th annual conference on Genetic and evolutionary computation, July 12-16, 2008, Atlanta, GA, USA [doi>10.1145/1389095.1389151]
• 10: Sridhar Hannenhalli , Pavel Pevzner, Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.178-189, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225112]
• 11: S. Hannenhalli , P. A. Pevzner, Transforming men into mice (polynomial algorithm for genomic distance problem), Proceedings of the 36th Annual Symposium on Foundations of Computer Science, p.581, October 23-25, 1995
• 12: G. Jean and M. Nikolski. Mining the semantics of genome super-blocks to infer ancestral architectures. Journal of Computational Biology, accepted for publication.
• 13: L. Ke, Zuren Feng, Zhigang Ren and Xiaoliang Wei An ant colony optimization approach for the multidimensional knapsack problem Journal of Heuristics, 2008.
• 14: J. F. Lefebvre, N. El-Mabrouk, E.Tillier, and D. Sankoff. Detection and validation of single gene inversions. In ISMB (Supplement of Bioinformatics), pages 190--196, 2003.
• 15: I.Milos. Mcmc genome rearrangement. Bioinformatics, 19 Suppl 2:ii130--ii137, 2003.
• 16: M. Ozery-Flato and R. Shamir. Two notes on genome rearrangement. J. Bioinformatics Comput. Biol., 1(1):71--94, 2003.
• 17: J.D. Palmer and L.A. Herbon. Plant mitochondrial DNA evolves rapidly in structure, but slowly in sequence Journal of Molecular Evolution, 28: 87--97, 1988.
• 18: C. Seoighe, Federspiel N.J.T., Hansen N., Bivolarovic V., Surzycki R., Tamse, R., Komp C., Huizar L., Davis R.W., Scherer S., Tait E., Shaw D.J., Harris, D., Murphy L., Oliver K., Taylor K., Rajandream M.A., Barrell B.G., and Wolfe K.H. Prevalence of small inversions in yeast gene order evolution. Proc. Natl. Acad. Sci. USA, 97:14433--14437, 2000.
• 19: A. Siepel. An algorithm to enumerate sorting reversals for signed permutations. Journal of Comp. Biol., 10(3--4): 575--597, 2003.
• 20: D. Sherman, T. Martin, M. Nikolski, C. Cayla, J.-L. Souciet, and P. Durrens. Genolevure: protein families and synteny among complete hemiascomycetous yeast proteomes and genomes. Nucleic Acids Research (NAR), Database Issue: D550--D554, 2008
• 21: Krister M. Swenson , Vaibhav Rajan , Yu Lin , Bernard M. Moret, Sorting Signed Permutations by Inversions in O(nlogn) Time, Proceedings of the 13th Annual International Conference on Research in Computational Molecular Biology, p.386-399, May 18-21, 2009, Tucson, Arizona [doi>10.1007/978-3-642-02008-7_28]
• 22: Eric Tannier , Anne Bergeron , Marie-France Sagot, Advances on sorting by reversals, Discrete Applied Mathematics, v.155 n.6-7, p.881-888, April, 2007 [doi>10.1016/j.dam.2005.02.033]
• 23: Glenn Tesler, Efficient algorithms for multichromosomal genome rearrangements, Journal of Computer and System Sciences, v.65 n.3, p.587-609, November 2002 [doi>10.1016/S0022-0000(02)00011-9]

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.3 LIFE AND MEDICAL SCIENCES
      Subjects: Biology and genetics

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms

Keywords:
ant colony optimization, genome rearrangement