A 1.375-approximation algorithm for sorting by transpositions

IEEE/ACM Transactions on Computational Biology and Bioinformatics
Isaac Elias, Tzvika Hartman

Abstract

Sorting permutations by transpositions is an important problem in genome rearrangements. A transposition is a rearrangement operation in which a segment is cut out of the permutation and pasted in a different location. The complexity of this problem is still open and it has been a 10-year-old open problem to improve the best known 1.5-approximation algorithm. In this paper, we provide a 1.375-approximation algorithm for sorting by transpositions. The algorithm is based on a new upper bound on the diameter of 3-permutations. In addition, we present some new results regarding the transposition diameter: we improve the lower bound for the transposition diameter of the symmetric group and determine the exact transposition diameter of simple permutations.

References

Sep 11, 2008·Journal of Computational Biology : a Journal of Computational Molecular Cell Biology·Simon Gog, Martin Bader
Jun 28, 2011·Journal of Computational Biology : a Journal of Computational Molecular Cell Biology·Jesun Sahariar FirozM Sohel Rahman
Dec 8, 2010·Bioinformatics·Haitao JiangDaming Zhu
Dec 5, 2009·BMC Bioinformatics·Ying Chih LinChunhung Richard Lin
Oct 18, 2013·Journal of Bioinformatics and Computational Biology·Ulisses Dias, Zanoni Dias
Sep 19, 2015·Journal of Computational Biology : a Journal of Computational Molecular Cell Biology·Luís Felipe I CunhaCelina M H de Figueiredo
Feb 23, 2011·IEEE/ACM Transactions on Computational Biology and Bioinformatics·Pedro Feijão, João Meidanis
Nov 7, 2006·IEEE/ACM Transactions on Computational Biology and Bioinformatics·Anthony Labarre
Apr 4, 2015·Algorithms for Molecular Biology : AMB·Gustavo Rodrigues GalvãoZanoni Dias
Oct 10, 2008·BMC Genomics·Feng YueJijun Tang
Jun 28, 2014·Journal of Bioinformatics and Computational Biology·Ulisses DiasZanoni Dias
Feb 17, 2017·Journal of Bioinformatics and Computational Biology·Carla Negri LintzmayerZanoni Dias
Jan 22, 2008·Bioinformatics·Simon GogEnno Ohlebusch
Jun 3, 2017·IEEE/ACM Transactions on Computational Biology and Bioinformatics·Tom HartmannMatthias Bernt
Feb 21, 2019·Journal of Computational Biology : a Journal of Computational Molecular Cell Biology·Andre Rodrigues OliveiraUlisses Dias
Jan 1, 2020·Journal of Computational Biology : a Journal of Computational Molecular Cell Biology·Klairton Lima BritoZanoni Dias
Nov 12, 2019·Algorithms for Molecular Biology : AMB·Andre Rodrigues OliveiraZanoni Dias
Aug 2, 2018·Algorithms for Molecular Biology : AMB·Andre Rodrigues OliveiraZanoni Dias
Apr 25, 2020·Journal of Bioinformatics and Computational Biology·Alexsandro Oliveira AlexandrinoZanoni Dias
Oct 22, 2020·Journal of Computational Biology : a Journal of Computational Molecular Cell Biology·Alexsandro Oliveira AlexandrinoZanoni Dias

Citations

May 31, 2001·Journal of Computational Biology : a Journal of Computational Molecular Cell Biology·P A PevznerC L Tang
Nov 6, 2001·Journal of Computational Biology : a Journal of Computational Molecular Cell Biology·D A BaderM Yan

Related Concepts

Transposition of Intestine (Disorder)
Cellular Transposition
Genome Mapping
Sorting - Cell Movement
Congenital Transposition
Sequence Determinations, DNA
Linkage Disequilibrium
Antineoplaston A10
DNA Sequence Rearrangement
Evolution, Molecular

Trending Feeds

COVID-19

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

Journal of Computational Biology : a Journal of Computational Molecular Cell Biology
Martin Bader, Enno Ohlebusch
Journal of Computational Biology : a Journal of Computational Molecular Cell Biology
D A BaderM Yan
Journal of Computational Biology : a Journal of Computational Molecular Cell Biology
Ying Chih LinChuan Yi Tang
IEEE/ACM Transactions on Computational Biology and Bioinformatics
Xin ChenTao Jiang
© 2020 Meta ULC. All rights reserved