research-article

Sorting genomes using almost-symmetric inversions

Authors:

Zanoni Dias,

Ulisses Dias,

Lenwood S. Heath,

João C. SetubalAuthors Info & Claims

SAC '12: Proceedings of the 27th Annual ACM Symposium on Applied Computing

Pages 1368 - 1374

https://doi.org/10.1145/2245276.2231993

Published: 26 March 2012 Publication History

Get Access

Abstract

Inversions are one of the most frequent large-scale rearrangements observed in actual genomes. While a large body of literature exists on mathematical problems related to the computation of the inversion distance between abstract genomes, these works generally do not take into account that most inversions in bacterial chromosomes are symmetric or roughly symmetric with respect to the origin of replication. We define a new problem: how to sort genomes (or permutations) using almost-symmetric inversions. We show an algorithm that can sort any permutation using only almost-symmetric inversions. Two variants of this algorithm are presented that have better performance in practice. We explore the question of determining the minimum number of almost-symmetric inversions needed to sort a genome by presenting lower and upper bounds and results for special permutation families. The results obtained are the first steps in exploring this interesting new problem.

References

[1]

D. A. Bader, B. M. E. Moret, and M. Yan. A linear-time algorithm for computing inversion distance between signed permutations with an experimental study. Journal of Computational Biology, 8(5): 483--491, 2001.

Crossref

Google Scholar

[2]

V. Bafna and P. A. Pevzner. Genome rearrangements and sorting by reversals. SIAM Journal on Computing, 25: 272--289, 1996.

Digital Library

Google Scholar

[3]

A. Bergeron. A very elementary presentation of the Hannenhalli-Pevzner theory. Discrete Applied Mathematics, 146: 134--145, 2005.

Digital Library

Google Scholar

[4]

A. Caprara. Sorting permutations by reversals and Eulerian cycle decompositions. SIAM Journal on Discrete Mathematics, 12: 91--110, 1999.

Digital Library

Google Scholar

[5]

A. E. Darling, I. Miklós, and M. A. Ragan. Dynamics of genome rearrangement in bacterial populations. PLoS Genetics, 4(7): e1000128, 2008.

Crossref

Google Scholar

[6]

J. A. Eisen, J. F. Heidelberg, O. White, and S. L. Salzberg. Evidence for symmetric chromosomal inversions around the replication origin in bacteria. Genome Biology, 1(6): research0011.1-0011.9, 2000.

Google Scholar

[7]

S. Hannenhalli and P. A. Pevzner. Transforming cabbage into turnip: Polynomial algorithm for sorting signed permutations by reversals. Journal of the ACM, 46(1): 1--27, 1999.

Digital Library

Google Scholar

[8]

J. Kececioglu and D. Sankoff. Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement. Algorithmica, 13(1--2): 180--210, 1995.

Google Scholar

[9]

E. Ohlebusch, M. I. Abouelhodaa, and K. Hockela. A linear time algorithm for the inversion median problem in circular bacterial genomes. Journal of Discrete Algorithms, 5: 637--646, 2007.

Digital Library

Google Scholar

[10]

E. Tannier, A. Bergeron, and M.-F. Sagot. Advances on sorting by reversals. Discrete Applied Mathematics, 155: 881--888, 2007.

Digital Library

Google Scholar

Cited By

View all

Baudet CDias UDias Z(2014)Length and Symmetry on the Sorting by Weighted Inversions ProblemAdvances in Bioinformatics and Computational Biology10.1007/978-3-319-12418-6_13(99-106)Online publication date: 2014
https://doi.org/10.1007/978-3-319-12418-6_13
Dias UBaudet CDias Z(2013)Greedy Randomized Search Procedure to Sort Genomes using Symmetric, Almost-Symmetric and Unitary InversionsProceedings of the International Conference on Bioinformatics, Computational Biology and Biomedical Informatics10.1145/2506583.2506614(181-190)Online publication date: 22-Sep-2013
https://dl.acm.org/doi/10.1145/2506583.2506614

Recommendations

Greedy Randomized Search Procedure to Sort Genomes using Symmetric, Almost-Symmetric and Unitary Inversions
BCB'13: Proceedings of the International Conference on Bioinformatics, Computational Biology and Biomedical Informatics

Genome Rearrangement is a field that addresses the problem of finding the minimum number of global operations that transform one given genome into another. In this work we develop an algorithm for three constrained versions of the event called inversion,...
A simulation tool for the study of symmetric inversions in bacterial genomes
RECOMB-CG'10: Proceedings of the 2010 international conference on Comparative genomics

We present the tool SIB that simulates genomic inversions in bacterial chromosomes. The tool simulates symmetric inversions but allows the appearance of nonsymmetric inversions by simulating small syntenic blocks frequently observed on bacterial genome ...
Sorting genomes by generalized translocations

Translocation is a prevalent rearrangement event in the evolution of multi-chromosomal species which exchanges ends between two chromosomes. A translocation is reciprocal if none of the exchanged ends is empty; otherwise, non-reciprocal. The problem of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SAC '12: Proceedings of the 27th Annual ACM Symposium on Applied Computing

March 2012

2179 pages

ISBN:9781450308571

DOI:10.1145/2245276

Conference Chairs:
Sascha Ossowski
University Rey Juan Carlos, Spain
,
Paola Lecca
The Microsoft Research - University of Trento COSBI, Italy

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 March 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Funding Sources

Conselho Nacional de Desenvolvimento Científico e Tecnológico

Conference

SAC 2012

Sponsor:

SIGAPP

SAC 2012: ACM Symposium on Applied Computing

March 26 - 30, 2012

Trento, Italy

Acceptance Rates

SAC '12 Paper Acceptance Rate 270 of 1,056 submissions, 26%;

Overall Acceptance Rate 1,650 of 6,669 submissions, 25%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
140
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Baudet CDias UDias Z(2014)Length and Symmetry on the Sorting by Weighted Inversions ProblemAdvances in Bioinformatics and Computational Biology10.1007/978-3-319-12418-6_13(99-106)Online publication date: 2014
https://doi.org/10.1007/978-3-319-12418-6_13
Dias UBaudet CDias Z(2013)Greedy Randomized Search Procedure to Sort Genomes using Symmetric, Almost-Symmetric and Unitary InversionsProceedings of the International Conference on Bioinformatics, Computational Biology and Biomedical Informatics10.1145/2506583.2506614(181-190)Online publication date: 22-Sep-2013
https://dl.acm.org/doi/10.1145/2506583.2506614

View Options

Login options

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

Cited By

Recommendations

Greedy Randomized Search Procedure to Sort Genomes using Symmetric, Almost-Symmetric and Unitary Inversions

A simulation tool for the study of symmetric inversions in bacterial genomes

Sorting genomes by generalized translocations