Sorting Circular Permutations by Super Short Reversals

被引:8
作者
Galvao, Gustavo Rodrigues [1 ]
Baudet, Christian [2 ,3 ]
Dias, Zanoni [1 ]
机构
[1] Univ Estadual Campinas, Inst Comp, Campinas, SP, Brazil
[2] Univ Lyon 1, CNRS, Lab Biometrie & Biol Evolut, Villeurbanne UMR5558, Villeurbanne, France
[3] Canc Res Ctr Lyon, Bioinformat Team, Ctr Leon Berard, Lyon, France
基金
巴西圣保罗研究基金会;
关键词
Genome rearrangement; short reversals; circular permutations; MICROBIAL GENOME DATABASE; MODELS; MBGD;
D O I
10.1109/TCBB.2016.2515594
中图分类号
Q5 [生物化学];
学科分类号
071010 ; 081704 ;
摘要
We consider the problem of sorting a circular permutation by super short reversals (i.e., reversals of length at most 2), a problem that finds application in comparative genomics. Polynomial-time solutions to the unsigned version of this problem are known, but the signed version remained open. In this paper, we present the first polynomial-time solution to the signed version of this problem. Moreover, we perform experiments for inferring phylogenies of two different groups of bacterial species and compare our results with the phylogenies presented in previous works. Finally, to facilitate phylogenetic studies based on the methods studied in this paper, we present a web tool for rearrangement-based phylogenetic inference using short operations, such as super short reversals.
引用
收藏
页码:620 / 633
页数:14
相关论文
共 25 条
[1]  
Bafna V., 2000, COMPARATIVE GENOMICS, V1, P199
[2]   Genome rearrangement distances and gene order phylogeny in γ-proteobacteria [J].
Belda, E ;
Moya, A ;
Silva, FJ .
MOLECULAR BIOLOGY AND EVOLUTION, 2005, 22 (06) :1456-1467
[3]   A draft genome of Yersinia pestis from victims of the Black Death [J].
Bos, Kirsten I. ;
Schuenemann, Verena J. ;
Golding, G. Brian ;
Burbano, Hernan A. ;
Waglechner, Nicholas ;
Coombes, Brian K. ;
McPhee, Joseph B. ;
DeWitte, Sharon N. ;
Meyer, Matthias ;
Schmedes, Sarah ;
Wood, James ;
Earn, David J. D. ;
Herring, D. Ann ;
Bauer, Peter ;
Poinar, Hendrik N. ;
Krause, Johannes .
NATURE, 2011, 478 (7370) :506-510
[4]   Measuring genome divergence in bacteria: A case study using Chlamydian data [J].
Dalevi, DA ;
Eriksen, N ;
Eriksson, K ;
Andersson, SGE .
JOURNAL OF MOLECULAR EVOLUTION, 2002, 55 (01) :24-36
[5]   progressiveMauve: Multiple Genome Alignment with Gene Gain, Loss and Rearrangement [J].
Darling, Aaron E. ;
Mau, Bob ;
Perna, Nicole T. .
PLOS ONE, 2010, 5 (06)
[6]   Dynamics of Genome Rearrangement in Bacterial Populations [J].
Darling, Aaron E. ;
Miklos, Istvan ;
Ragan, Mark A. .
PLOS GENETICS, 2008, 4 (07)
[7]   Group-theoretic models of the inversion process in bacterial genomes [J].
Egri-Nagy, Attila ;
Gebhardt, Volker ;
Tanaka, Mark M. ;
Francis, Andrew R. .
JOURNAL OF MATHEMATICAL BIOLOGY, 2014, 69 (01) :243-265
[8]  
Felsenstein J., 2005, PHYLIP (phylogeny inference package) version 3.6
[9]   Sorting Circular Permutations by Bounded Transpositions [J].
Feng, Xuerong ;
Chitturi, Bhadrachalam ;
Sudborough, Hal .
ADVANCES IN COMPUTATIONAL BIOLOGY, 2010, 680 :725-736
[10]  
Fertin Guillaume, 2009, Combinatorics of Genome Rearrangements. Computational Molecular Biology