Exploring the Solution Space of Sorting by Reversals, with Experiments and an Application to Evolution

ABSTRACT

In comparative genomics, algorithms that sort permutations by reversals are often used to propose evolutionary scenarios of rearrangements between species. One of the main problems of such methods is that they give one solution while the number of optimal solutions is huge, with no criteria to discriminate among them. Bergeron et al. started to give some structure to the set of optimal solutions, in order to be able to deliver more presentable results than only one solution or a complete list of all solutions. However, no algorithm exists so far to compute this structure except through the enumeration of all solutions, which takes too much time even for small permutations. Bergeron et al. state as an open problem the design of such an algorithm. We propose in this paper an answer to this problem, that is, an algorithm which gives all the classes of solutions and counts the number of solutions in each class, with a better theoretical and practical complexity than the complete enumeration method. We give an example of how to reduce the number of classes obtained, using further constraints. Finally, we apply our algorithm to analyse the possible scenarios of rearrangement between mammalian sex chromosomes.

REFERENCES

• 1: Yasmine Ajana , Jean-François Lefebvre , Elisabeth R. M. Tillier , Nadia El-Mabrouk, Exploring the Set of All Minimal Sequences of Reversals - An Application to Test the Replication-Directed Reversal Hypothesis, Proceedings of the Second International Workshop on Algorithms in Bioinformatics, p.300-315, September 17-21, 2002
• 2: D.A. Bader, B.M.E. Moret, and M. Yan, "A Linear-Time Algorithm for Computing Inversion Distances Between Signed Permutations with an Experimental Study," J. Computational Biology, vol. 8, no. 5, pp. 483-491, 2001.
• 3: S. Berard, A. Bergeron, and C. Chauve, "Conserved Structures in Evolution Scenarios," RCG 2004, Lecture Notes in Bioinformatics, vol. 3388, pp. 1-15, 2005.
• 4: 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]
• 5: A. Bergeron, C. Chauve, T. Hartmann, and K. St-Onge, "On the Properties of Sequences of Reversals That Sort a Signed Permutation," Proc. Journées Ouvertes Biologie, Informatique et Mathématiques (JOBIM '02), pp. 99-108, 2002.
• 6: A. Bergeron, S. Heber, and J. Stoye, "Common Intervals and Sorting by Reversals: A Marriage of Necessity," Bioinformatics, vol. 18 (Suppl. 2), pp. S54-63, 2002.
• 7: A. Bergeron, J. Mixtacki, and J. Stoye, "The Inversion Distance Problem," Math. of Evolution and Phylogeny, O. Gascuel, ed., pp. 262-290, Oxford Univ. Press, 2005.
• 8: M.D.V Braga, M.-F. Sagot, C. Scornavacca, and E. Tannier, "The Solution Space of Sorting by Reversals," Proc. Int'l Symp. Bioinformatics Research and Applications (ISBRA '07), vol. 4463, pp. 293-304, 2007.
• 9: Graham Brightwell , Peter Winkler, Counting linear extensions is #P-complete, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.175-181, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103441]
• 10: Grzegorz Rozenberg , Volker Diekert, The Book of Traces, World Scientific Publishing Co., Inc., River Edge, NJ, 1995
• 11: Yoan Diekmann , Marie-France Sagot , Eric Tannier, Evolution under Reversals: Parsimony and Conservation of Common Intervals, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.4 n.2, p.301-309, April 2007 [doi>10.1109/TCBB.2007.1042]
• 12: R.P. Dilworth, "A Decomposition Theorem for Partially Ordered Sets," Annals of Math., vol. 51, pp. 161-166, 1950.
• 13: D.R. Fulkerson, "Note on Dilworth's Decomposition Theorem for Partially Ordered Sets," Proc. Am. Math. Soc., vol. 7, pp. 701-702, 1956.
• 14: Y. Han, "Improving the Efficiency of Sorting by Reversals," Proc. Int'l Conf. Bioinformatics and Computational Biology, 2006.
• 15: Sridhar Hannenhalli , Pavel A. Pevzner, Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals, Journal of the ACM (JACM), v.46 n.1, p.1-27, Jan. 1999 [doi>10.1145/300515.300516]
• 16: B.T. Lahn and D.C. Page, "Four Evolutionary Strata on the Human X Chromosome," Science, vol. 286, pp. 964-967, 1999.
• 17: Z. Li, L. Wang, and K. Zhang, "Algorithmic Approaches for Genome Rearrangement: A Review," IEEE Trans. Systems, Man, and Cybernetics, vol. 36, pp. 636-648, 2006.
• 18: S. Ohno, Sex Chromosomes and Sex-Linked Genes. Springer, 1967.
• 19: M.T. Ross et al., "The DNA Sequence of the Human X Chromosome," Nature, vol. 434, pp. 325-337, 2005.
• 20: A. Siepel, "An Algorithm to Enumerate Sorting Reversals for Signed Permutations," J. Computational Biology, vol. 10, pp. 575- 597, 2003.
• 21: H. Skaletsky et al., "The Male-Specific Region of the Human Y Chromosome is a Mosaic of Discrete Sequence Classes," Nature, vol. 423, pp. 825-837, 2003.
• 22: G. Steiner, "An Algorithm to Generate the Ideals of a Partial Order," Operations Research Letters, vol. 5, no. 6, pp. 317-320, 1986.
• 23: G. Steiner, "Polynomial Algorithms to Count Linear Extensions in Certain Posets," Congressus Numerantium, vol. 75, pp. 71-90, 1990.
• 24: 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]

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching; Sequencing and scheduling

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Permutations and combinations

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology

General Terms:
Algorithms, Design

Keywords:
genome rearrangements, signed permutations, sorting by reversals, common intervals, perfect sorting, evolution, sex chromosomes