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

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.
Type de document :
Communication dans un congrès
Jing Gao. Proceedings of the 4th ACM Conference on Bioinformatics, Computational Biology and Biomedical Informatics (ACM BCB 2013), Sep 2013, Maryland, United States. pp.181--190, 2013, 〈http://dl.acm.org/citation.cfm?doid=2506583.2506614〉. 〈10.1145/2506583.2506614〉
Liste complète des métadonnées

Littérature citée [29 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00922670
Contributeur : Marie-France Sagot <>
Soumis le : mardi 4 juillet 2017 - 12:24:34
Dernière modification le : jeudi 11 janvier 2018 - 06:22:33
Document(s) archivé(s) le : vendredi 15 décembre 2017 - 00:15:59

Fichier

p181-Dias.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Ulisses Dias, Christian Baudet, Zanoni Dias. Greedy Randomized Search Procedure to Sort Genomes using Symmetric, Almost-Symmetric and Unitary Inversions. Jing Gao. Proceedings of the 4th ACM Conference on Bioinformatics, Computational Biology and Biomedical Informatics (ACM BCB 2013), Sep 2013, Maryland, United States. pp.181--190, 2013, 〈http://dl.acm.org/citation.cfm?doid=2506583.2506614〉. 〈10.1145/2506583.2506614〉. 〈hal-00922670〉

Partager

Métriques

Consultations de la notice

216

Téléchargements de fichiers

16