A general heuristic for genome rearrangement problems

Journal of Bioinformatics and Computational Biology
Ulisses DiasZanoni Dias


In this paper, we present a general heuristic for several problems in the genome rearrangement field. Our heuristic does not solve any problem directly, it is rather used to improve the solutions provided by any non-optimal algorithm that solve them. Therefore, we have implemented several algorithms described in the literature and several algorithms developed by ourselves. As a whole, we implemented 23 algorithms for 9 well known problems in the genome rearrangement field. A total of 13 algorithms were implemented for problems that use the notions of prefix and suffix operations. In addition, we worked on 5 algorithms for the classic problem of sorting by transposition and we conclude the experiments by presenting results for 3 approximation algorithms for the sorting by reversals and transpositions problem and 2 approximation algorithms for the sorting by reversals problem. Another algorithm with better approximation ratio can be found for the last genome rearrangement problem, but it is purely theoretical with no practical implementation. The algorithms we implemented in addition to our heuristic lead to the best practical results in each case. In particular, we were able to improve results on the sorting by transpositions pr...Continue Reading


Feb 17, 2017·Journal of Bioinformatics and Computational Biology·Carla Negri LintzmayerZanoni Dias


Nov 7, 2006·IEEE/ACM Transactions on Computational Biology and Bioinformatics·Isaac Elias, Tzvika Hartman
Nov 1, 2007·Academic Medicine : Journal of the Association of American Medical Colleges·Andrew H Brainard, Heather C Brislen
Oct 18, 2013·Journal of Bioinformatics and Computational Biology·Ulisses Dias, Zanoni Dias

Related Concepts

Sequence Inversion
Cellular Transposition
Sorting - Cell Movement
Congenital Transposition
Suffix brand of benzoylprop-ethyl
DNA Sequence Rearrangement
Gene Rearrangement
Online Mendelian Inheritance In Man
Computational Molecular Biology

Trending Feeds


Coronaviruses encompass a large family of viruses that cause the common cold as well as more serious diseases, such as the ongoing outbreak of coronavirus disease 2019 (COVID-19; formally known as 2019-nCoV). Coronaviruses can spread from animals to humans; symptoms include fever, cough, shortness of breath, and breathing difficulties; in more severe cases, infection can lead to death. This feed covers recent research on COVID-19.

Sexual Dimorphism in Neurodegeneration

There exist sex differences in neurodevelopmental and neurodegenerative disorders. For instance, multiple sclerosis is more common in women, whereas Parkinson’s disease is more common in men. Here is the latest research on sexual dimorphism in neurodegeneration

HLA Genetic Variation

HLA genetic variation has been found to confer risk for a wide variety of diseases. Identifying these associations and understanding their molecular mechanisms is ongoing and holds promise for the development of therapeutics. Find the latest research on HLA genetic variation here.

Super-resolution Microscopy

Super-resolution microscopy is the term commonly given to fluorescence microscopy techniques with resolutions that are not limited by the diffraction of light. Here are the latest discoveries pertaining to super-resolution microscopy.

Genetic Screens in iPSC-derived Brain Cells

Genetic screening is a critical tool that can be employed to define and understand gene function and interaction. This feed focuses on genetic screens conducted using induced pluripotent stem cell (iPSC)-derived brain cells.

Brain Lower Grade Glioma

Low grade gliomas in the brain form from oligodendrocytes and astrocytes and are the slowest-growing glioma in adults. Discover the latest research on these brain tumors here.

CD4/CD8 Signaling

Cluster of differentiation 4 and 8 (CD8 and CD8) are glycoproteins founds on the surface of immune cells. Here is the latest research on their role in cell signaling pathways.

Alignment-free Sequence Analysis Tools

Alignment-free sequence analyses have been applied to problems ranging from whole-genome phylogeny to the classification of protein families, identification of horizontally transferred genes, and detection of recombined sequences. Here is the latest research.

Chronic Fatigue Syndrome

Chronic fatigue syndrome is a disease characterized by unexplained disabling fatigue; the pathology of which is incompletely understood. Discover the latest research on chronic fatigue syndrome here.

Related Papers

IEEE/ACM Transactions on Computational Biology and Bioinformatics
Isaac Elias, Tzvika Hartman
Journal of Computational Biology : a Journal of Computational Molecular Cell Biology
Jesun Sahariar FirozM Sohel Rahman
IEEE/ACM Transactions on Computational Biology and Bioinformatics
Xingqin QiYing Xu
© 2020 Meta ULC. All rights reserved