Approximations for the Weighted Reversal, Transposition, and Indel Distance Problem with Intergenic Region Information
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911348352352256 |
|---|---|
| author | Siqueira, Gabriel Alexandrino, Alexsandro Oliveira Dias, Zanoni |
| author_facet | Siqueira, Gabriel Alexandrino, Alexsandro Oliveira Dias, Zanoni |
| contents | Genome rearrangement distances are an established method in genome comparison. Works in this area may include various rearrangement operations representing large-scale mutations, gene orientation information, the number of nucleotides in intergenic regions, and weights reflecting the expected frequency of each operation. In this article, we model genomes containing at most one copy of each gene by considering gene sequences, with orientations, and representing intergenic regions according to their nucleotide lengths. We looked at a problem called Weighted Reversal, Transposition, and Indel Distance, which seeks the minimal cost sequence composed by the rearrangement operations of reversals, transposition, and indels, capable of transforming one genome into another. We leverage a structure called Labeled Intergenic Breakpoint Graph to show an algorithm for that problem with guaranteed approximations considering some sets of weights for the operations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_25016 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Approximations for the Weighted Reversal, Transposition, and Indel Distance Problem with Intergenic Region Information Siqueira, Gabriel Alexandrino, Alexsandro Oliveira Dias, Zanoni Data Structures and Algorithms Genome rearrangement distances are an established method in genome comparison. Works in this area may include various rearrangement operations representing large-scale mutations, gene orientation information, the number of nucleotides in intergenic regions, and weights reflecting the expected frequency of each operation. In this article, we model genomes containing at most one copy of each gene by considering gene sequences, with orientations, and representing intergenic regions according to their nucleotide lengths. We looked at a problem called Weighted Reversal, Transposition, and Indel Distance, which seeks the minimal cost sequence composed by the rearrangement operations of reversals, transposition, and indels, capable of transforming one genome into another. We leverage a structure called Labeled Intergenic Breakpoint Graph to show an algorithm for that problem with guaranteed approximations considering some sets of weights for the operations. |
| title | Approximations for the Weighted Reversal, Transposition, and Indel Distance Problem with Intergenic Region Information |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2512.25016 |