Paper Info
Title
Sorting by Reversals, Transpositions, and Indels on Both Gene Order and Intergenic Sizes.
Abstract
During the evolutionary process, the genome is affected by various genome rearrangements, which are events that modify large stretches of the genetic material. In the literature, several models were designed to estimate the number of events that occurred during the evolution, but these models represent genomes as a sequence of genes, overlooking the genetic material between consecutive genes. However, recent studies show that taking into account the genetic material present between consecutive genes can be more realistic. Reversal and transposition are genome rearrangements widely studied in the literature. A reversal inverts a segment of the genome while a transposition swaps the positions of two consecutive segments. Genomes also undergo non-conservative events (events that alter the amount of genetic material) such as insertion and deletion, which insert and remove genetic material from intergenic regions of the genome, respectively. We study problems considering both gene order and intergenic regions size. We investigate the reversal distance between two genomes in two scenarios: with and without non-conservative events. For both problems, we show that they belong to NP-hard problems class and we present a 4-approximation algorithm. We also study the reversal and transposition distance between two genomes (and the variation with non-conservative events) and we present a 6-approximation algorithm.
Year
DOI
Venue
2019
10.1007/978-3-030-20242-2_3
BIOINFORMATICS RESEARCH AND APPLICATIONS, ISBRA 2019
Keywords
Field
DocType
Genome rearrangements,Intergenic regions,Approximation algorithms
Genome,Transposition (music),Approximation algorithm,Gene,Computer science,Sorting,Artificial intelligence,Intergenic region,Computational biology,Machine learning,Indel
Conference
Volume
ISSN
Citations 
11490
0302-9743
0
PageRank 
References 
Authors
0.34
0
6
Name
Order
Citations
PageRank
Klairton Lima Brito101.01
Géraldine Jean2516.72
Guillaume Fertin356957.84
Andre Rodrigues Oliveira406.76
Ulisses Dias54113.23
Zanoni Dias626244.40