Counting Sorting Scenarios and Intermediate Genomes for the Rank Distance

An important problem in genome comparison is the genome sorting problem, that is, the problem of finding a sequence of basic operations that transforms one genome into another whose length (possibly weighted) equals the distance between them. These sequences are called optimal sorting scenarios. How...

Full description

Saved in:
Bibliographic Details
Published in:IEEE/ACM transactions on computational biology and bioinformatics 2024-05, Vol.21 (3), p.316-327
Main Authors: Zanetti, Joao Paulo Pereira, Oliveira, Lucas Peres, Meidanis, Joao, Chindelevitch, Leonid
Format: Article
Language:English
Subjects:
Algorithms
Bioinformatics
Breakpoint graph
enumeration
Extremities
genome rearrangements
Genomes
Genomics
Graph theory
Nucleotide sequence
rank distance
Sorting
Sorting algorithms
Transforms
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:An important problem in genome comparison is the genome sorting problem, that is, the problem of finding a sequence of basic operations that transforms one genome into another whose length (possibly weighted) equals the distance between them. These sequences are called optimal sorting scenarios. However, there is usually a large number of such scenarios, and a naïve algorithm is very likely to be biased towards a specific type of scenario, impairing its usefulness in real-world applications. One way to go beyond the traditional sorting algorithms is to explore all possible solutions, looking at all the optimal sorting scenarios instead of just an arbitrary one. Another related approach is to analyze all the intermediate genomes, that is, all the genomes that can occur in an optimal sorting scenario. In this article, we show how to enumerate the optimal sorting scenarios and the intermediate genomes between any two given genomes, under the rank distance.
ISSN:1545-5963
1557-9964
DOI:10.1109/TCBB.2023.3277733