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

Ulisses Dias 1, * Christian Baudet 2, 3 Zanoni Dias 1
* Corresponding author
2 Baobab
PEGASE - Département PEGASE [LBBE]
3 BAMBOO - An algorithmic view on genomes, cells, and environments
Inria Grenoble - Rhône-Alpes, LBBE - Laboratoire de Biométrie et Biologie Evolutive - UMR 5558
Abstract : 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, which occurs when a chromosome breaks at two locations called breakpoints and the DNA between the breakpoints is reversed. The constrained versions are called symmetric, almost-symmetric and unitary inversions. In this paper, we present a greedy randomized search procedure to find the minimum number of such operations between two genomes. Our approach is, to our knowledge, the first genome rearrangement problem modeled using this metaheuristic. Our model is an iterative process in which each iteration receives a feasible solution whose neighborhood is investigated for a better solution. This search uses greediness to shape the candidate list and randomness to select elements from the list. A previous greedy heuristic was used as an initial solution. In almost every case, we were able to improve that initial solution by providing a new sequence of inversions that uses less operations. For permutations of size 10, our solutions were, on average, 5 inversions shorter than the initial solution. For permutations of size 15 and 20, our solutions were, on average, 10 and 16 inversions shorter than the initial solution, respectively. For longer permutations ranging from 25 to 50 elements, we generated solutions that were, on average, 20-22 inversions shorter than the initial solution. We believe that the method proposed in this work can be adjusted to other genome rearrangement problems.
Complete list of metadatas

Cited literature [29 references]  Display  Hide  Download

https://hal.inria.fr/hal-00922670
Contributor : Marie-France Sagot <>
Submitted on : Tuesday, July 4, 2017 - 12:24:34 PM
Last modification on : Wednesday, November 20, 2019 - 2:37:21 AM
Long-term archiving on : Friday, December 15, 2017 - 12:15:59 AM

File

p181-Dias.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Ulisses Dias, Christian Baudet, Zanoni Dias. Greedy Randomized Search Procedure to Sort Genomes using Symmetric, Almost-Symmetric and Unitary Inversions. Proceedings of the 4th ACM Conference on Bioinformatics, Computational Biology and Biomedical Informatics (ACM BCB 2013), ACM Special Interest Group on Bioinformatics, Computational Biology, and Biomedical Informatics, Sep 2013, Maryland, United States. pp.181--190, ⟨10.1145/2506583.2506614⟩. ⟨hal-00922670⟩

Share

Metrics

Record views

333

Files downloads

309