Greedy Randomized Search Procedure to Sort Genomes using Symmetric, Almost-Symmetric and Unitary Inversions - Archive ouverte HAL Access content directly
Conference Papers Year : 2013

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

(1) , (2, 3) , (1)
1
2
3

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.
Fichier principal
Vignette du fichier
p181-Dias.pdf (555.62 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-00922670 , version 1 (04-07-2017)

Identifiers

Cite

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⟩
154 View
141 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More