EUVIMEDEUVIMED entdecken
Crossref

A Barrier for Further Approximating Sorting by Transpositions

Luiz A G Silva iD, Luis A B Kowada, Maria E M T Walter

Journal of Computational Biology · 2023

DOI: 10.1089/cmb.2023.0138 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of Computational Biology, 2023. Verfasst von Luiz A G Silva und 2 weiteren Autor:innen. Beteiligte Einrichtung: Departamento de Ciência da Computação, Universidade de Brasília, Brasília, Brazil. Hauptthemen laut MEDLINE: Algorithms, Genome. Die Arbeit wurde bisher 2-mal zitiert (Crossref) und nennt 15 Literaturangaben.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

The transposition distance problem is a classical problem in genome rearrangements, which seeks to determine the minimum number of transpositions needed to transform a linear chromosome into another represented by the permutations π and σ, respectively. This article focuses on the equivalent problem of sorting by transpositions (SBT), where σ is the identity permutation ι. Specifically, we investigate palisades, a family of permutations that are "hard" to sort, as they require numerous transpositions above the celebrated lower bound devised by Bafna and Pevzner. By determining the transposition distance of palisades, we were able to provide the exact transposition diameter for 3-permutations (TD3), a special subset of the symmetric group Sn, essential for the study of approximate solutions for SBT using the simplification technique. The exact value for TD3 has remained unknown since Elias and Hartman showed an upper bound for it. Another consequence of determining the transposition distance of palisades is that, using as lower bound the one by Bafna and Pevzner, it is impossible to guarantee approximation ratios lower than 1.375 when approximating SBT. This finding has significant implications for the study of SBT, as this problem has been the subject of intense research efforts for the past 25 years.

Schlagwörter

MeSH-Schlagwörter (MEDLINE)

AlgorithmsGenomeGene RearrangementModels, Genetic

Stichwörter der Autor:innen

genome rearrangementssorting by transpositionstransposition distance problem

Autor:innen und Institutionen

  • Departamento de Ciência da Computação, Universidade de Brasília, Brasília, Brazil.
  • Instituto de Computação, Universidade Federal Fluminense, Niterói, Brazil.

ORCID-Profile: Luiz A G Silva

Zitieren

APA

Silva, L. A. G., Kowada, L. A. B., & Walter, M. E. M. T. (2023). A Barrier for Further Approximating Sorting by Transpositions. Journal of Computational Biology. https://doi.org/10.1089/cmb.2023.0138

Vancouver

Silva LAG, Kowada LAB, Walter MEMT. A Barrier for Further Approximating Sorting by Transpositions. Journal of Computational Biology. 2023. doi:10.1089/cmb.2023.0138

BibTeX
@article{Silva2023,
  author = {Silva, Luiz A G and Kowada, Luis A B and Walter, Maria E M T},
  title = {A Barrier for Further Approximating Sorting by Transpositions},
  journal = {Journal of Computational Biology},
  year = {2023},
  doi = {10.1089/cmb.2023.0138}
}
Kostenlos starten →