Sorting signed circular permutations by super short operations

One way to estimate the evolutionary distance between two given genomes is to determine the minimum number of large-scale mutations, or , that are necessary to transform one into the other. In this context, genomes can be represented as ordered sequences of genes, each gene being represented by a si...

Full description

Saved in:
Bibliographic Details
Published in:Algorithms for molecular biology 2018-07, Vol.13 (1), p.13-13, Article 13
Main Authors: Oliveira, Andre R, Fertin, Guillaume, Dias, Ulisses, Dias, Zanoni
Format: Article
Language:English
Subjects:
Algorithms
Bioinformatics
Circular permutations
Circularity
Classification
Computational Complexity
Computer Science
Data Structures and Algorithms
Evolution
Gene sequencing
Genes
Genome rearrangements
Genomes
Genomics
Mutation
Permutations
Polynomials
Sorting algorithms
Super short operations
Transposition
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:One way to estimate the evolutionary distance between two given genomes is to determine the minimum number of large-scale mutations, or , that are necessary to transform one into the other. In this context, genomes can be represented as ordered sequences of genes, each gene being represented by a signed integer. If no gene is repeated, genomes are thus modeled as signed permutations of the form , and in that case we can consider without loss of generality that one of them is the identity permutation , and that we just need to the other (i.e., transform it into ). The most studied genome rearrangement events are , where a segment of the genome is reversed and reincorporated at the same location; and , where two consecutive segments are exchanged. Many variants, e.g., combining different types of (possibly constrained) rearrangements, have been proposed in the literature. One of them considers that the number of genes involved, in a reversal or a transposition, is never greater than two, which is known as the problem of sorting by (or SSOs). All problems considering SSOs in permutations have been shown to be in , except for one, namely sorting signed circular permutations by super short reversals and super short transpositions. Here we fill this gap by introducing a new graph structure called   and providing a series of intermediate results, which allows us to design a polynomial algorithm for sorting signed circular permutations by super short reversals and super short transpositions.
ISSN:1748-7188
1748-7188
DOI:10.1186/s13015-018-0131-6