Super short operations on both gene order and intergenic sizes

The evolutionary distance between two genomes can be estimated by computing a minimum length sequence of operations, called , that transform one genome into another. Usually, a genome is modeled as an ordered sequence of genes, and most of the studies in the genome rearrangement literature consist i...

Full description

Saved in:
Bibliographic Details
Published in:Algorithms for molecular biology 2019-11, Vol.14 (1), p.21-21, Article 21
Main Authors: Oliveira, Andre R, Jean, Géraldine, Fertin, Guillaume, Dias, Ulisses, Dias, Zanoni
Format: Article
Language:English
Subjects:
Algorithms
Anopheles
Approximation algorithms
Bioinformatics
Computer Science
Genes
Genetic research
Genome rearrangements
Genomes
Genomics
Intergenic regions
Mathematical models
Nucleotides
Super short operations
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The evolutionary distance between two genomes can be estimated by computing a minimum length sequence of operations, called , that transform one genome into another. Usually, a genome is modeled as an ordered sequence of genes, and most of the studies in the genome rearrangement literature consist in shaping biological scenarios into mathematical models. For instance, allowing different genome rearrangements operations at the same time, adding constraints to these rearrangements (e.g., each rearrangement can affect at most a given number of genes), considering that a rearrangement implies a cost depending on its length rather than a unit cost, etc. Most of the works, however, have overlooked some important features inside genomes, such as the presence of sequences of nucleotides between genes, called . In this work, we investigate the problem of computing the distance between two genomes, taking into account both gene order and intergenic sizes. The genome rearrangement operations we consider here are constrained types of reversals and transpositions, called (SSRs) and (SSTs), which affect up to two (consecutive) genes. We denote by (SSOs) any SSR or SST. We show 3-approximation algorithms when the orientation of the genes is not considered when we allow SSRs, SSTs, or SSOs, and 5-approximation algorithms when considering the orientation for either SSRs or SSOs. We also show that these algorithms improve their approximation factors when the input permutation has a higher number of inversions, where the approximation factor decreases from 3 to either 2 or 1.5, and from 5 to either 3 or 2.
ISSN:1748-7188
1748-7188
DOI:10.1186/s13015-019-0156-5