article

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

Authors:

Marília D. V. Braga,

Marie-France Sagot,

Celine Scornavacca,

Eric TannierAuthors Info & Claims

IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), Volume 5, Issue 3

Pages 348 - 356

https://doi.org/10.1109/TCBB.2008.16

Published: 01 July 2008 Publication History

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]

Y. Ajana, J.F. Lefebvre, E. Tillier, and N. El-Mabrouk, "Exploring the Set of All Minimal Sequences of Reversals--An Application to Test the Replication-Directed Reversal Hypothesis," Proc. Second Int'l Workshop Algorithms in Bioinformatics (WABI '02), vol. 2452, pp. 300-315, 2002.

Digital Library

[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.

Digital Library

[4]

S. Berard, A. Bergeron, C. Chauve, and C. Paul, "Perfect Sorting by Reversals Is Not Always Difficult," IEEE/ACM Trans. Computational Biology and Bioinformatics, vol. 4, no. 1, pp. 4-16, Jan.-Mar. 2007.

Digital Library

[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.

Digital Library

[9]

G. Brightwell and P. Winkler, "Counting Linear Extensions is #P-Complete," Proc. 23rd Ann. ACM Symp. Theory of Computing (STOC), 1991.

Digital Library

[10]

The Book of Traces, V. Diekert, G. Rozenberg, eds. World Scientific, 1995.

Digital Library

[11]

Y. Diekmann, M.F. Sagot, and E. Tannier, "Evolution under Reversals: Parsimony and Conservation of Common Intervals," IEEE/ACM Trans. Computational Biology and Bioinformatics, vol. 4, no. 2, pp. 301-309, Apr.-June 2007. (A preliminary version appeared in COCOON 2005, LNCS 3595, 42-51, 2005.)

Digital Library

[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]

S. Hannenhalli and P. Pevzner, "Transforming Cabbage into Turnip (Polynomial Algorithm for Sorting Signed Permutations by Reversals)," J. ACM, vol. 46, pp. 1-27, 1999.

Digital Library

[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.

Digital Library

[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.

Digital Library

[23]

G. Steiner, "Polynomial Algorithms to Count Linear Extensions in Certain Posets," Congressus Numerantium, vol. 75, pp. 71-90, 1990.

[24]

E. Tannier, A. Bergeron, and M.-F. Sagot, "Advances on Sorting by Reversals," Discrete Applied Math., vol. 155, nos. 6-7, pp. 881-888, 2007.

Digital Library

Cited By

Wang YMary ASagot MSinaimeri B(2023)A General Framework for Enumerating Equivalence Classes of SolutionsAlgorithmica10.1007/s00453-023-01131-185:10(3003-3023)Online publication date: 4-May-2023
https://dl.acm.org/doi/10.1007/s00453-023-01131-1
Wang B(2016)A New Efficient Algorithm for the All Sorting Reversals Problem with No Bad ComponentsIEEE/ACM Transactions on Computational Biology and Bioinformatics10.1109/TCBB.2015.247680313:4(599-609)Online publication date: 1-Jul-2016
https://dl.acm.org/doi/10.1109/TCBB.2015.2476803
Amritanjali Sahoo G(2013)Listing Sorting Sequences of Reversals and TranslocationsProceedings of the International Conference on Bioinformatics, Computational Biology and Biomedical Informatics10.1145/2506583.2512381(712-713)Online publication date: 22-Sep-2013
https://dl.acm.org/doi/10.1145/2506583.2512381
Show More Cited By

Index Terms

Recommendations

Evolution under Reversals: Parsimony and Conservation of Common Intervals

In comparative genomics, gene order data is often modeled as signed permutations. A classical problem for genome comparison is to detect common intervals in permutations, that is, genes that are colocalized in several species, indicating that they ...
Genome rearrangements and sorting by reversals
SFCS '93: Proceedings of the 1993 IEEE 34th Annual Foundations of Computer Science

Sequence comparison in molecular biology is in the beginning of a major paradigm shift-a shift from gene comparison based on local mutations to chromosome comparison based on global rearrangements. In the simplest form the problem of gene rearrangements ...
Genome Rearrangements and Sorting by Reversals

Sequence comparison in molecular biology is in the beginning of a major paradigm shift---a shift from gene comparison based on local mutations (i.e., insertions, deletions, and substitutions of nucleotides) to chromosome comparison based on global ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Computational Biology and Bioinformatics

IEEE/ACM Transactions on Computational Biology and Bioinformatics Volume 5, Issue 3

July 2008

159 pages

ISSN:1545-5963

Issue’s Table of Contents

Publisher

IEEE Computer Society Press

Washington, DC, United States

Publication History

Published: 01 July 2008

Published in TCBB Volume 5, Issue 3

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
151
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)1

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wang YMary ASagot MSinaimeri B(2023)A General Framework for Enumerating Equivalence Classes of SolutionsAlgorithmica10.1007/s00453-023-01131-185:10(3003-3023)Online publication date: 4-May-2023
https://dl.acm.org/doi/10.1007/s00453-023-01131-1
Wang B(2016)A New Efficient Algorithm for the All Sorting Reversals Problem with No Bad ComponentsIEEE/ACM Transactions on Computational Biology and Bioinformatics10.1109/TCBB.2015.247680313:4(599-609)Online publication date: 1-Jul-2016
https://dl.acm.org/doi/10.1109/TCBB.2015.2476803
Amritanjali Sahoo G(2013)Listing Sorting Sequences of Reversals and TranslocationsProceedings of the International Conference on Bioinformatics, Computational Biology and Biomedical Informatics10.1145/2506583.2512381(712-713)Online publication date: 22-Sep-2013
https://dl.acm.org/doi/10.1145/2506583.2512381
Baudet CDias ZGrossman RRzhetsky AKim SWang W(2011)Partial enumeration of solutions traces for the problem of sorting by signed reversalsProceedings of the 2nd ACM Conference on Bioinformatics, Computational Biology and Biomedicine10.1145/2147805.2147884(505-507)Online publication date: 1-Aug-2011
https://dl.acm.org/doi/10.1145/2147805.2147884
Baudet CDias ZShin SOssowski SSchumacher MPalakal MHung C(2010)An improved algorithm to enumerate all traces that sort a signed permutation by reversalsProceedings of the 2010 ACM Symposium on Applied Computing10.1145/1774088.1774416(1521-1525)Online publication date: 22-Mar-2010
https://dl.acm.org/doi/10.1145/1774088.1774416
Baudet CDias ZTulpan DPalakal MAbdul Nazeer KR. A(2010)Chronological order of reversal events on Rickettsia genusProceedings of the International Symposium on Biocomputing10.1145/1722024.1722026(1-5)Online publication date: 15-Feb-2010
https://dl.acm.org/doi/10.1145/1722024.1722026
Bernt MChen MMerkle DWang HChao KMiddendorf M(2009)Finding All Sorting Tandem Duplication Random Loss OperationsProceedings of the 20th Annual Symposium on Combinatorial Pattern Matching - Volume 557710.5555/3127091.3127118(301-313)Online publication date: 22-Jun-2009
https://dl.acm.org/doi/10.5555/3127091.3127118
Vyahhi NGoëffon ANikolski MSherman DRothlauf F(2009)Swarming along the evolutionary branches sheds light on genome rearrangement scenariosProceedings of the 11th Annual conference on Genetic and evolutionary computation10.1145/1569901.1569935(241-246)Online publication date: 8-Jul-2009
https://dl.acm.org/doi/10.1145/1569901.1569935

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents