EUVIMEDEUVIMED entdecken
Crossref

Rearrangement distance with reversals, indels, and moves in intergenic regions on signed and unsigned permutations

Klairton Lima Brito iD, Andre Rodrigues Oliveira iD, Alexsandro Oliveira Alexandrino iD, Ulisses Dias iD, Zanoni Dias iD

Journal of Bioinformatics and Computational Biology · 2023

DOI: 10.1142/s0219720023500099 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of Bioinformatics and Computational Biology, 2023. Verfasst von Klairton Lima Brito und 4 weiteren Autor:innen. Beteiligte Einrichtung: Institute of Computing, University of Campinas, 1251 Albert Einstein Avenue, Campinas, São Paulo, Brazil. Hauptthemen laut MEDLINE: Gene Rearrangement, Models, Genetic. Die Arbeit nennt 24 Literaturangaben. Gefördert von: Conselho Nacional de Desenvolvimento Científico e Tecnologico, Coordenação de Aperfeiçoamento de Pessoal de Nível Superior, Fundação de Amparo à Pesquisa do Estado de São Paulo.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Genome rearrangement events are widely used to estimate a minimum-size sequence of mutations capable of transforming a genome into another. The length of this sequence is called distance, and determining it is the main goal in genome rearrangement distance problems. Problems in the genome rearrangement field differ regarding the set of rearrangement events allowed and the genome representation. In this work, we consider the scenario where the genomes share the same set of genes, gene orientation is known or unknown, and intergenic regions (structures between a pair of genes and at the extremities of the genome) are taken into account. We use two models, the first model allows only conservative events (reversals and moves), and the second model includes non-conservative events (insertions and deletions) in the intergenic regions. We show that both models result in NP-hard problems no matter if gene orientation is known or unknown. When the information regarding the orientation of genes is available, we present for both models an approximation algorithm with a factor of 2. For the scenario where this information is unavailable, we propose a 4-approximation algorithm for both models.

Schlagwörter

MeSH-Schlagwörter (MEDLINE)

Gene RearrangementModels, GeneticDNA, IntergenicGenomeMutationAlgorithms

Stichwörter der Autor:innen

Genome rearrangementsapproximation algorithmscomplexity analysis

Substanzen

DNA, Intergenic

Autor:innen und Institutionen

  • Institute of Computing, University of Campinas, 1251 Albert Einstein Avenue, Campinas, São Paulo, Brazil.
  • Computing and Informatics Department, Mackenzie Presbyterian University, 905 Mackenzie Avenue, Barueri, São Paulo, Brazil.
  • School of Technology, University of Campinas, 1888 Paschoal Marmo Street, Limeira, São Paulo, Brazil.

ORCID-Profile: Klairton Lima Brito, Andre Rodrigues Oliveira, Alexsandro Oliveira Alexandrino, Ulisses Dias, Zanoni Dias

Förderung

  • Conselho Nacional de Desenvolvimento Científico e Tecnologico
  • Coordenação de Aperfeiçoamento de Pessoal de Nível Superior
  • Fundação de Amparo à Pesquisa do Estado de São Paulo

Zitieren

APA

Brito, K. L., Oliveira, A. R., Alexandrino, A. O., Dias, U., & Dias, Z. (2023). Rearrangement distance with reversals, indels, and moves in intergenic regions on signed and unsigned permutations. Journal of Bioinformatics and Computational Biology. https://doi.org/10.1142/s0219720023500099

Vancouver

Brito KL, Oliveira AR, Alexandrino AO, Dias U, Dias Z. Rearrangement distance with reversals, indels, and moves in intergenic regions on signed and unsigned permutations. Journal of Bioinformatics and Computational Biology. 2023. doi:10.1142/s0219720023500099

BibTeX
@article{Brito2023,
  author = {Brito, Klairton Lima and Oliveira, Andre Rodrigues and Alexandrino, Alexsandro Oliveira and Dias, Ulisses and Dias, Zanoni},
  title = {Rearrangement distance with reversals, indels, and moves in intergenic regions on signed and unsigned permutations},
  journal = {Journal of Bioinformatics and Computational Biology},
  year = {2023},
  doi = {10.1142/s0219720023500099}
}
Kostenlos starten →