@article{1975-dweighter,
author = {Harry Dweighter},
title = {{Problem E2569}},
journal = {{American Mathematical Monthly}},
volume = {82},
year = {1975},
pages = {1010},
number = {}
}
@article{1979-gates-papadimitriou,
author = {William H. Gates and Christos H. Papadimitriou},
title = {{Bounds for Sorting by Prefix Reversal}},
journal = {{Discrete Mathematics}},
volume = {27},
number = {1},
pages = {47--57},
year = {1979}
}
@article{1985-jerrum,
author = {Mark R. Jerrum},
title = {{The Complexity of Finding Minimum-length Generator Sequences}},
journal = {{Theoretical Computer Science}},
volume = {36},
pages = {265--289},
year = {1985},
number = {2-3}
}
@article{1987-aigner-west,
author = {Martin Aigner and Douglas B. West},
title = {{Sorting by Insertion of Leading Elements}},
journal = {{Journal of Combinatorial Theory Series A}},
volume = {45},
number = {2},
year = {1987},
pages = {306--309}
}
@article{1987-saitou-nei,
author = {Naruya Saitou and Masatoshi Nei},
journal = {{Molecular Biology and Evolution}},
pages = {406--425},
title = {{The Neighbor-joining Method: A New Method for Reconstructing
Phylogenetic Trees}},
volume = {4},
year = {1987},
number = {4}
}
@incollection{1993-heydari-sudborough,
author = {Mohammad H. Heydari and Ivan H. Sudborough},
title = {{On Sorting by Prefix Reversals and the Diameter of Pancake
Networks}},
booktitle = {{Proceedings of the 1st Heinz Nixdorf Symposium on Parallel
Architectures and Their Efficient Use}},
series = {{Lecture Notes in Computer Science}},
editor = {F. Meyer and B. Monien and A. Rosenberg},
publisher = {{Springer-Verlag Berlin Heidelberg}},
address = {Heidelberg/Berlin, Germany},
pages = {218--227},
volume = {678},
year = {1993}
}
@article{1993-lakshmivarahan-etal,
title = {{Symmetry in Interconnection Networks Based on Cayley Graphs of
Permutation Groups: a Survey}},
author = {S. Lakshmivarahan and Jung-Sing Jwo and Sudarshan Dhall},
journal = {{Parallel Computing}},
volume = {19},
number = {4},
pages = {361--407},
year = {1993}
}
@incollection{1994-kececioglu-sankoff,
author = {John D. Kececioglu and David Sankoff},
title = {{Efficient Bounds for Oriented Chromosome Inversion Distance}},
booktitle = {{Proceedings of the 5th Annual Symposium on Combinatorial
Pattern Matching (CPM'1994)}},
year = {1994},
series = {{Lecture Notes in Computer Science}},
volume = {807},
pages = {307--325},
publisher = {{Springer-Verlag Berlin Heidelberg}},
address = {Heidelberg/Berlin, Germany},
editor = {M. Crochemore and D. Gusfield}
}
@inproceedings{1995-hannenhalli-pevzner,
author = {Sridhar Hannenhalli and Pavel A. Pevzner},
title = {{Transforming Men into Mice (Polynomial Algorithm for Genomic
Distance Problem)}},
pages = {581--592},
booktitle = {{Proceedings of the 36th Annual Symposium on Foundations of
Computer Science (FOCS'1995)}},
publisher = {{IEEE Computer Society Press}},
address = {Washington, DC, USA},
year = {1995}
}
@article{1995-hannenhalli-etal,
author = {Sridhar Hannenhalli and Colombe Chappey and Eugene V. Koonin and
Pavel A. Pevzner},
journal = {{Genomics}},
pages = {299--311},
title = {{Genome Sequence Comparison and Scenarios for Gene Rearrangements:
a Test Case}},
volume = {30},
year = {1995}
}
@inproceedings{1995-pevzner-waterman,
title = {{Open Combinatorial Problems in Computational Molecular Biology}},
author = {Pavel A. Pevzner and Michael S. Waterman},
booktitle = {{Proceedings of the 3rd Israel Symposium on the Theory of
Computing Systems (ISTCS'1995)}},
year = {1995},
pages = {158--173},
publisher = {{IEEE Computer Society}},
address = {Washington, DC, USA}
}
@article{1995-kececioglu-sankoff,
author = {John D. Kececioglu and David Sankoff},
title = {{Exact and Approximation Algorithms for Sorting by Reversals, with
Application to Genome Rearrangement}},
journal = {{Algorithmica}},
pages = {180--210},
volume = {13},
year = {1995}
}
@inproceedings{1995-kececioglu-ravi,
author = {John D. Kececioglu and R. Ravi},
title = {{Of Mice and Men: Algorithms for Evolutionary Distances Between
Genomes with Translocation}},
pages = {604--613},
booktitle = {{Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete
Algorithms (SODA'1995)}},
publisher = {{Society for Industrial and Applied Mathematics}},
address = {Philadelphia, PA, USA},
year = {1995},
editor = {K. Clarkson}
}
@article{1995-cohen-blum,
author = {David S. Cohen and Manuel Blum},
title = {{On the Problem of Sorting Burnt Pancakes}},
journal = {{Discrete Applied Mathematics}},
volume = {61},
number = {2},
year = {1995},
pages = {105--120}
}
@article{1995-bafna-pevzner,
author = {Vineet Bafna and Pavel A. Pevzner},
journal = {{Molecular Biology and Evolution}},
pages = {239--246},
title = {{Sorting by Reversals: Genome Rearrangements in Plant Organelles
and Evolutionary History of X Chromosome}},
volume = {12},
number = {2},
year = {1995}
}
@inproceedings{1995-hannenhalli,
author = {Sridhar Hannenhalli},
title = {{Polynomial-time Algorithm for Computing Translocation Distance
between Genomes}},
booktitle = {{Proceedings of the 6th Annual Symposium on Combinatorial
Pattern Matching (CPM'1995)}},
series = {{Lecture Notes in Computer Science}},
volume = {937},
pages = {162--176},
year = {1995},
editor = {Z. Galil and E. Ukkonen},
publisher = {{Springer Berlin Heidelberg}},
address = {Heidelberg/Berlin, Germany}
}
@article{1996-bafna-pevzner,
author = {Vineet Bafna and Pavel A. Pevzner},
title = {{Genome Rearrangements and Sorting by Reversals}},
journal = {{SIAM Journal on Computing}},
volume = {25},
number = {2},
year = {1996},
pages = {272--289}
}
@article{1996-chen-skiena,
author = {Ting Chen and Steven S. Skiena},
title = {{Sorting with Fixed-Length Reversals}},
journal = {{Discrete Applied Mathematics}},
volume = {71},
number = {1-3},
pages = {269--295},
year = {1996}
}
@article{1996-christie,
author = {David A. Christie},
title = {{Sorting Permutations by Block-Interchanges}},
journal = {{Information Processing Letters}},
volume = {60},
number = {4},
pages = {165--169},
year = {1996}
}
@article{1996-blanchette-etal,
author = {Mathieu Blanchette and Takashi Kunisawa and David Sankoff},
title = {{Parametric Genome Rearrangement}},
journal = {Gene},
volume = {172},
number = {1},
pages = {{GC11--GC17}},
year = {1996}
}
@inproceedings{1996-hannenhalli-pevzner,
author = {Sridhar Hannenhalli and Pavel Pevzner},
title = {{To Cut ... or Not to Cut (Applications of Comparative Physical
Maps in Molecular Evolution)}},
booktitle = {{Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete
Algorithms (SODA'1996)}},
year = {1996},
pages = {304--313},
publisher = {{Society for Industrial and Applied Mathematics}},
address = {Philadelphia, PA, USA},
editor = {E. Tardos}
}
@inproceedings{1997a-meidanis-etal,
author = {Jo{\~a}o Meidanis and Maria E. M. T. Walter and Zanoni Dias},
title = {{Dist{\^a}ncia de Revers{\~a}o de Cromossomos Circulares}},
booktitle = {{Proceedings of the 24th Semin{\'a}rio Integrado de Software e
Hardware (SEMISH'1997)}},
note = {{In Portuguese}},
pages = {119--131},
year = {1997}
}
@inproceedings{1997b-meidanis-etal,
title = {{Transposition Distance Between a Permutation and its Reverse}},
author = {Jo{\~a}o Meidanis and Maria E. M. T. Walter and Zanoni Dias},
booktitle = {{Proceedings of the 4th South American Workshop on String
Processing (WSP'1997)}},
editor = {R. Baeza-Yates},
pages = {70--79},
publisher = {{Carleton University Press}},
address = {Ontario, Canada},
year = {1997}
}
@article{1997-heydari-sudborough,
title = {{On the Diameter of the Pancake Network}},
author = {Mohammad H. Heydari and Ivan H. Sudborough},
journal = {{Journal of Algorithms}},
volume = {25},
number = {1},
pages = {67--94},
year = {1997}
}
@techreport{1997-guyer-etal,
title = {{Subsequence and Run Heuristics for Sorting by Transpositions}},
author = {Scott A. Guyer and Lenwood S. Heath and John P. Vergara},
year = {1997},
number = {{TR-97-20}},
institution = {{Virginia Polytechnic Institute \& State University}},
address = {Blacksburg, VA, USA}
}
@article{1997-altschul-etal,
author = {Stephen F. Altschul and Thomas L. Madden and Alejandro A. Schaffer
and Jinghui Zhang and Zheng Zhang and Webb Miller and David J.
Lipman},
journal = {{Nucleic Acids Research}},
pages = {3389--3402},
title = {{Gapped BLAST and PSI-BLAST: a new Generation of Protein Database
Search Programs}},
volume = {25},
year = {1997}
}
@inproceedings{1998a-christie,
author = {David A. Christie},
title = {{A 3/2-Approximation Algorithm for Sorting by Reversals}},
booktitle = {{Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete
Algorithms (SODA'1998)}},
year = {1998},
pages = {244--252},
publisher = {{Society for Industrial and Applied Mathematics}},
address = {Philadelphia, PA, USA},
editor = {H. Karloff}
}
@phdthesis{1998b-christie,
author = {David A. Christie},
title = {{Genome Rearrangement Problems}},
school = {{Department of Computing Science, University of Glasgow}},
year = {1998}
}
@article{1998-bafna-pevzner,
author = {Vineet Bafna and Pavel A. Pevzner},
title = {{Sorting by Transpositions}},
journal = {{SIAM Journal on Discrete Mathematics}},
volume = {11},
number = {2},
year = {1998},
pages = {224--240}
}
@inproceedings{1998-walter-etal,
author = {Maria E. M. T. Walter and Zanoni Dias and Jo{\~a}o Meidanis},
booktitle = {{Proceedings of the 5th International Symposium on String
Processing and Information Retrieval (SPIRE'1998)}},
title = {{Reversal and Transposition Distance of Linear Chromosomes}},
year = {1998},
pages = {96--102},
publisher = {{IEEE Computer Society}},
address = {Los Alamitos, CA, USA}
}
@article{1998-heath-vergara,
author = {Lenwood S. Heath and John P. C. Vergara},
title = {{Sorting by Bounded Block-moves}},
journal = {{Discrete Applied Mathematics}},
volume = {88},
number = {1-3},
pages = {181--206},
year = {1998}
}
@article{1998-eisen,
author = {Jonathan A. Eisen},
journal = {{Genome Research}},
pages = {163--167},
title = {{Phylogenomics: Improving Functional Predictions for
Uncharacterized Genes by Evolutionary Analysis}},
volume = {8},
year = {1998}
}
@article{1998-sankoff-blanchette,
author = {David Sankoff and Mathieu Blanchette},
journal = {{Journal of Computational Biology}},
number = {3},
pages = {555--70},
title = {{Multiple Genome Rearrangement and Breakpoint Phylogeny}},
volume = {5},
year = {1998}
}
@phdthesis{1999-walter,
author = {Maria E. M. T. Walter},
school = {{Institute of Computing, University of Campinas}},
title = {{Algoritmos para Problemas em Rearranjo de Genomas}},
note = {{In Portuguese}},
year = {1999}
}
@article{1999-caprara,
author = {Alberto Caprara},
title = {{Sorting Permutations by Reversals and Eulerian Cycle
Decompositions}},
journal = {{SIAM Journal on Discrete Mathematics}},
volume = {12},
number = {1},
year = {1999},
pages = {91--110}
}
@article{1999-hannenhalli-pevzner,
author = {Sridhar Hannenhalli and Pavel A. Pevzner},
title = {{Transforming Cabbage into Turnip: Polynomial Algorithm for Sorting
Signed Permutations by Reversals}},
journal = {{Journal of the ACM}},
volume = {46},
number = {1},
year = {1999},
pages = {1--27}
}
@article{1999-gu-etal,
title = {{A 2-Approximation Algorithm for Genome Rearrangements by Reversals
and Transpositions}},
author = {Qian-Ping Gu and Shietung Peng and Ivan H. Sudborough},
journal = {{Theoretical Computer Science}},
volume = {210},
number = {2},
pages = {327--339},
year = {1999}
}
@incollection{1999-berman-karpinski,
author = {Piotr Berman and Marek Karpinski},
title = {{On Some Tighter Inapproximability Results (Extended Abstract)}},
year = {1999},
booktitle = {{Proceedings of the 26th International Colloquium on Automata,
Languages and Programming (ICAL'1999)}},
volume = {1644},
series = {{Lecture Notes in Computer Science}},
editor = {J. Wiedermann and P. E. Boas and M. Nielsen},
publisher = {{Springer-Verlag}},
address = {London, UK},
pages = {200--209}
}
@article{1999a-caprara-etal,
author = {Alberto Caprara and Giuseppe Lancia and See K. Ng},
journal = {{DIMACS Series in Discrete Mathematics and Theoretical Computer
Science}},
pages = {213--226},
title = {{A Column-generation Based Branch-and-bound Algorithm for Sorting
by Reversals}},
volume = {47},
year = {1999}
}
@inproceedings{2000-walter-etal,
author = {Maria E. M. T. Walter and Zanoni Dias and Jo{\~a}o Meidanis},
title = {{A New Approach for Approximating The Transposition Distance}},
booktitle = {{Proceedings of the 7th String Processing and Information
Retrieval (SPIRE'2000)}},
year = {2000},
pages = {199--208},
publisher = {{IEEE Computer Society}},
address = {Los Alamitos, CA, USA},
editor = {F. M. Titsworth}
}
@inproceedings{2000-caprara-etal,
author = {Alberto Caprara and Giuseppe Lancia and See K. Ng},
title = {{Fast Practical Solution of Sorting by Reversals}},
booktitle = {{Proceedings of the 11th ACM-SIAM Annual Symposium on Discrete
Algorithms (SODA'2000)}},
pages = {12--21},
publisher = {{Society for Industrial and Applied Mathematics}},
address = {Philadelphia, PA, USA},
year = {2000},
editor = {D. Shmoys}
}
@incollection{2000-meidanis-dias,
author = {Jo{\~a}o Meidanis and Zanoni Dias},
title = {{An Alternative Algebraic Formalism for Genome Rearrangements}},
booktitle = {{Comparative Genomics: Empirical and Analytical Approaches to
Gene Order Dynamics, Map Alignment and Evolution of Gene Families}},
pages = {213--223},
volume = {1},
year = {2000},
editor = {D. Sankoff and J. H. Nadeau},
publisher = {{Springer Science+Business Media}},
address = {Dordrecht, Netherlands}
}
@techreport{2000a-meidanis-etal,
author = {Jo{\~a}o Meidanis and Maria E. M. T. Walter and Zanoni Dias},
institution = {{Institute of Computing, University of Campinas}},
number = {{IC-00-23}},
title = {{Reversal Distance of Signed Circular Chromosomes}},
year = {2000}
}
@techreport{2000b-meidanis-etal,
author = {Jo{\~a}o Meidanis and Maria E. M. T. Walter and Zanoni Dias},
institution = {{Institute of Computing, University of Campinas}},
number = {{IC-00-16}},
title = {{A Lower Bound on the Reversal and Transposition Diameter}},
year = {2000}
}
@article{2000-eisen-etal,
author = {Jonathan A. Eisen and John F. Heidelberg and Owen White and Steven
L. Salzberg},
journal = {{Genome Biology}},
number = {6},
pages = {research0011.1--0011.9},
title = {{Evidence for Symmetric Chromosomal Inversions Around the
Replication Origin in Bacteria}},
volume = {1},
year = {2000}
}
@article{2000-heath-vergara,
title = {{Sorting by Short Block-Moves}},
author = {Lenwood S. Heath and John Paul C. Vergara},
journal = {{Algorithmica}},
volume = {28},
number = {3},
pages = {323--352},
year = {2000},
publisher = {Springer}
}
@article{2001-eriksson-etal,
title = {{Sorting a Bridge Hand}},
author = {Henrik Eriksson and Kimmo Eriksson and Johan Karlander and Lars
Svensson and Johan Wastlund},
journal = {{Discrete Mathematics}},
volume = {241},
number = {1-3},
year = {2001},
pages = {289--300}
}
@article{2001-bader-etal,
author = {David A. Bader and Bernard M. E. Moret and Mi Yan},
title = {{A Linear-Time Algorithm for Computing Inversion Distance Between
Signed Permutations with an Experimental Study}},
journal = {{Journal of Computational Biology}},
year = {2001},
volume = {8},
pages = {483--491}
}
@article{2001-christie-irving,
author = {David A. Christie and Robert W. Irving},
title = {{Sorting Strings by Reversals and by Transpositions}},
journal = {{SIAM Journal on Discrete Mathematics}},
volume = {14},
number = {2},
year = {2001},
pages = {193--206}
}
@article{2001-lin-xue,
title = {{Signed Genome Rearrangement by Reversals and Transpositions: Models
and Approximations}},
journal = {{Theoretical Computer Science}},
volume = {259},
number = {1-2},
pages = {513--531},
year = {2001},
author = {Guo-Hui Lin and Guoliang Xue}
}
@inproceedings{2001-dias-meidanis,
author = {Zanoni Dias and Jo{\~a}o Meidanis},
title = {{Genome Rearrangements Distance by Fusion, Fission, and
Transposition is Easy}},
booktitle = {{Proceedings of the 8th String Processing and Information
Retrieval (SPIRE'2001)}},
year = {2001},
publisher = {{IEEE Computer Society}},
address = {Los Alamitos, CA, USA},
editor = {B. Werner},
pages = {250--253}
}
@article{2001-moret-etal,
author = {Bernard M. Moret and Li-San. Wang and Tandy Warnow and Stacia K.
Wyman},
journal = {{Bioinformatics}},
pages = {{S165--S173}},
title = {{New Approaches for Reconstructing Phylogenies from Gene Order
Data}},
volume = {{17 Suppl 1}},
year = {2001}
}
@article{2001-caprara-etal,
author = {Alberto Caprara and Giuseppe Lancia and See-Kiong Ng},
title = {{Sorting Permutations by Reversals Through Branch-and-Price}},
journal = {{INFORMS Journal on Computing}},
volume = {13},
number = {3},
pages = {224-244},
year = {2001}
}
@phdthesis{2002-dias,
author = {Zanoni Dias},
title = {{Rearranjo de Genomas: Uma Colet{\^a}nea de Artigos}},
school = {{University of Campinas, Institute of Computing}},
year = {2002},
note = {{In Portuguese}}
}
@incollection{2002a-dias-meidanis,
author = {Zanoni Dias and Jo{\~a}o Meidanis},
title = {{Sorting by Prefix Transpositions}},
booktitle = {{Proceedings of the 9th International Symposium on String
Processing and Information Retrieval (SPIRE'2002)}},
series = {{Lecture Notes in Computer Science}},
volume = {2476},
year = {2002},
pages = {65--76},
publisher = {{Springer-Verlag Berlin Heidelberg New York}},
address = {Berlin/Heidelberg, Germany},
editor = {A. H. F. Laender and A. L. Oliveira}
}
@techreport{2002b-dias-meidanis,
author = {Zanoni Dias and Jo{\~a}o Meidanis},
institution = {{Institute of Computing, University of Campinas}},
number = {{IC-02-01}},
title = {{The Genome Rearrangement Distance Problem with Arbitrary Weights}},
year = {2002}
}
@incollection{2002-berman-etal,
author = {Piotr Berman and Sridhar Hannenhalli and Marek Karpinski},
title = {{1.375-Approximation Algorithm for Sorting by Reversals}},
booktitle = {{Proceedings of the 10th Annual European Symposium on
Algorithms (ESA'2002)}},
series = {{Lecture Notes in Computer Science}},
volume = {2461},
year = {2002},
pages = {200--210},
publisher = {{Springer-Verlag Berlin Heidelberg New York}},
address = {Berlin/Heidelberg, Germany},
editor = {R. M{\"o}hring and R. Raman}
}
@article{2002-meidanis-etal,
title = {{A Lower Bound on the Reversal and Transposition Diameter}},
author = {Jo{\~a}o Meidanis and Maria E. M. T. Walter and Zanoni Dias},
journal = {{Journal of Computational Biology}},
volume = {9},
number = {5},
pages = {743--745},
year = {2002}
}
@article{2002-pinter-skiena,
author = {Ron Y. Pinter and Steven Skiena},
title = {{Genomic Sorting with Length-Weighted Reversals}},
journal = {{Genome Informatics}},
year = {2002},
volume = {13},
pages = {2002}
}
@article{2002-eriksen,
title = {{(1+$\epsilon$)-Approximation of Sorting by Reversals and
Transpositions}},
author = {Niklas Eriksen},
journal = {{Theoretical Computer Science}},
volume = {289},
number = {1},
pages = {517--529},
year = {2002}
}
@article{2002-caprara-rizzi,
title = {{Improved Approximation for Breakpoint Graph Decomposition and
Sorting by Reversals}},
author = {Alberto Caprara and Romeo Rizzi},
year = {2002},
journal = {{Journal of Combinatorial Optimization}},
volume = {6},
number = {2},
pages = {157--182}
}
@article{2002-bourque-pevzner,
author = {Guillaume Bourque and Pavel A. Pevzner},
journal = {{Genome Research}},
number = {1},
pages = {26--36},
title = {{Genome-scale Evolution: Reconstructing Gene Orders in the
Ancestral Species}},
volume = {12},
year = {2002}
}
@incollection{2002-ajana-etal,
author = {Yasmine Ajana and Jean-Fran{\c c}ois Lefebvre and Elisabeth R. M.
Tillier and Nadia El-Mabrouk},
title = {{Exploring the Set of All Minimal Sequences of Reversals - An
Application to Test the Replication-directed Reversal Hypothesis}},
booktitle = {{Proceedings of the 2nd International Workshop on
Algorithms in Bioinformatics (WABT'2002)}},
series = {{Lecture Notes in Computer Science}},
volume = {2452},
publisher = {{Springer-Verlag Berlin Heidelberg}},
address = {Heidelberg, Germany},
year = {2002},
pages = {300--315},
editor = {R. Guig{\'o} and D. Gusfield}
}
@article{2002-tesler,
author = {Glenn Tesler},
title = {{GRIMM: Genome Rearrangements Web Server}},
volume = {18},
number = {3},
pages = {492--493},
year = {2002},
journal = {{Bioinformatics}}
}
@inproceedings{2002-siepel,
author = {Adam C. Siepel},
title = {{An Algorithm to Enumerate All Sorting Reversals}},
booktitle = {{Proceedings of the 6th Annual International Conference on
Computational Biology (RECOMB'2002)}},
year = {2002},
pages = {281--290},
address = {New York, NY, USA},
publisher = {ACM},
editor = {G. Myers and S. Hannenhalli and D. Sankoff and S. Istrail and P.
Pevzner and M. Waterman}
}
@article{2003-bass-sudborough,
author = {Douglas W. Bass and Ivan H. Sudborough},
title = {{Pancake Problems with Restricted Prefix Reversals and some
Corresponding Cayley Networks}},
journal = {{Journal of Parallel and Distributed Computing}},
volume = {63},
number = {3},
pages = {327--336},
year = {2003}
}
@incollection{2003-walter-etal,
author = {Maria E. M. T. Walter and Luiz R. A. F. Curado and Adilton G. Oliveira},
booktitle = {{Proceedings of the 14th Annual Symposium on Combinatorial
Pattern Matching (CPM'2003)}},
pages = {372--383},
series = {{Lecture Notes in Computer Science}},
title = {{Working on the Problem of Sorting by Transpositions on Genome
Rearrangements}},
volume = {2676},
year = {2003},
editor = {R. Baeza-Yates and E. Ch{\'a}vez and M. Crochemore},
publisher = {{Springer Berlin Heidelberg}},
address = {Berlin/Heidelberg, Germany}
}
@article{2003-achaz-etal,
author = {Guillaume Achaz and Eric Coissac and Pierre Netter and Eduardo P.
C. Rocha},
journal = {{Genetics}},
number = {4},
pages = {1279--1289},
title = {{Associations Between Inverted Repeats and the Structural Evolution
of Bacterial Genomes}},
volume = {164},
year = {2003}
}
@article{2003-heath-vergara,
title = {{Sorting by Short Swaps}},
author = {Lenwood S. Heath and John Paul C. Vergara},
journal = {{Journal of Computational Biology}},
volume = {10},
number = {5},
pages = {775--789},
year = {2003},
publisher = {Mary Ann Liebert, Inc.}
}
@article{2004-lin-jiang,
title = {{A Further Improved Approximation Algorithm for Breakpoint Graph
Decomposition}},
author = {Guohui Lin and Tao Jiang},
year = {2004},
journal = {{Journal of Combinatorial Optimization}},
volume = {8},
number = {2},
pages = {183--194}
}
@incollection{2004-swidan-etal,
title = {{Sorting by Length-Weighted Reversals: Dealing with Signs and
Circularity}},
author = {Firas Swidan and Michael A. Bender and Dongdong Ge and Simai He
and Haodong Hu and Ron Y. Pinter},
year = {2004},
booktitle = {{Combinatorial Pattern Matching}},
volume = {3109},
series = {{Lecture Notes in Computer Science}},
editor = {S. Sahinalp and S. Muthukrishnan and U. Dogrusoz},
publisher = {{Springer Berlin Heidelberg}},
address = {Heidelberg, Germany},
pages = {32--46}
}
@article{2004-darling-etal,
author = {Aaron E. Darling and Bob Mau and Frederick R. Blattner and Nicole
T. Perna},
journal = {{Genome Research}},
number = {7},
pages = {1394--1403},
title = {{Mauve: Multiple Alignment of Conserved Genomic Sequence with
Rearrangements}},
volume = {14},
year = {2004}
}
@mastersthesis{2004-honda,
author = {M. I. Honda},
school = {{Department of Computer Science, University of Brasilia, Brazil}},
title = {{Implementation of the Algorithm of Hartman for the Problem of
Sorting by Transpositions}},
year = {2004}
}
@inproceedings{2004-tannier-sagot,
author = {Eric Tannier and Marie-France Sagot},
booktitle = {{Proceedings of the 15th Annual Symposium on Combinatorial
Pattern Matching (CPM'2004)}},
pages = {1--13},
title = {{Sorting by Reversals in Subquadratic Time}},
year = {2004},
series = {{Lecture Notes in Computer Science}},
volume = {3109},
editor = {S. C. Sahinalp and S. Muthukrishnan and U. Dogrusoz},
publisher = {Springer Berlin Heidelberg},
address = {Berlin/Heidelberg, Germany}
}
@inproceedings{2004-chrobak-etal,
author = {Marek Chrobak and Petr Kolman and Ji{\v{r}}{\'i} Sgall},
editor = {K. Jansen and S. Khanna and J. D. P. Rolim and D Ron},
title = {{The Greedy Algorithm for the Minimum Common String Partition
Problem}},
booktitle = {{Proceedings of the 7th International Workshop on Approximation
Algorithms for Combinatorial Optimization Problems (APPROX'2004),
and 8th International Workshop on Randomization and Computation
(RANDOM'2004)}},
year = {2004},
publisher = {Springer Berlin Heidelberg},
address = {Berlin, Heidelberg},
pages = {84--95}
}
@inproceedings{2005-fischer-ginzinger,
author = {Johannes Fischer and Simon W. Ginzinger},
title = {{A 2-Approximation Algorithm for Sorting by Prefix Reversals}},
booktitle = {{Proceedings of the 13th Annual European Conference on
Algorithms (ESA'2005)}},
year = {2005},
pages = {415--425},
publisher = {{Springer Berlin Heidelberg}},
address = {Berlin, Heidelberg},
series = {{Lecture Notes in Computer Science}},
volume = {3669},
editor = {G. S. Brodal and S. Leonardi}
}
@article{2005-bergeron,
author = {Anne Bergeron},
title = {{A Very Elementary Presentation of the Hannenhalli-Pevzner Theory}},
journal = {{Discrete Applied Mathematics}},
volume = {146},
number = {2},
year = {2005},
pages = {134--145}
}
@article{2005-hartman-sharan,
author = {Tzvika Hartman and Roded Sharan},
title = {{A 1.5-Approximation Algorithm for Sorting by Transpositions and
Transreversals}},
journal = {{Journal of Computer and System Sciences}},
volume = {70},
number = {3},
year = {2005},
pages = {300--320}
}
@inproceedings{2005-labarre,
author = {Anthony Labarre},
title = {{A New Tight Upper Bound on the Transposition Distance}},
booktitle = {{Proceedings of the 5th International Conference on Algorithms
in Bioinformatics (WABI'2005)}},
year = {2005},
pages = {216--227},
publisher = {{Springer Berlin Heidelberg}},
address = {Berlin, Heidelberg},
series = {{Lecture Notes in Computer Science}},
volume = {3692},
editor = {R. Casadio and G. Myers}
}
@article{2005-nguyen-etal,
author = {Thach C. Nguyen and Hieu T. Ngo and Nguyen B. Nguyen},
title = {{Sorting by Restricted-Length-Weighted Reversals}},
journal = {{Genomics Proteomics \& Bioinformatics}},
volume = {3},
number = {2},
year = {2005},
pages = {120--127}
}
@incollection{2005-blin-rizzi,
author = {Guillaume Blin and Romeo Rizzi},
title = {{Conserved Interval Distance Computation Between Non-trivial
Genomes}},
year = {2005},
booktitle = {{Computing and Combinatorics}},
volume = {3595},
series = {{Lecture Notes in Computer Science}},
editor = {L. Wang},
publisher = {{Springer Berlin Heidelberg}},
address = {Heidelberg, Germany},
pages = {22--31}
}
@article{2005-radcliffe-etal,
author = {Andrew J. Radcliffe and Alex D. Scott and Elizabeth L. Wilmer},
title = {{Reversals and Transpositions Over Finite Alphabets}},
journal = {{SIAM Journal on Discrete Mathematics}},
volume = {19},
number = {1},
pages = {224--244},
year = {2005}
}
@mastersthesis{2005-fortuna,
author = {Vinicius J. Fortuna},
school = {{Institute of Computing, University of Campinas}},
title = {{Dist{\^a}ncias de Transposi{\c c}{\~a}o entre Genomas}},
year = {2005},
note = {{In Portuguese}}
}
@article{2005-larget-etal,
author = {Bret Larget and Donald L. Simon and Joseph B. Kadane and Deborah Sweet},
journal = {{Molecular Biology and Evolution}},
number = {3},
pages = {486--95},
title = {{A Bayesian Analysis of Metazoan Mitochondrial Genome
Arrangements}},
volume = {22},
year = {2005}
}
@article{2005-walter-etal,
author = {Maria E. M. T. Walter and Mauro C. Sobrinho and Eugenia T. G.
Oliveira and Lorena S. Soares and Adilton G. Oliveira and Thelmo E.
S. Martins and Tiago M. Fonseca},
journal = {{Discrete Algorithm}},
pages = {342--361},
title = {{Improving the Algorithm of Bafna and Pevzner for the Problem of
Sorting by Transpositions: a Practical Approach}},
volume = {3},
year = {2005}
}
@inproceedings{2005-ohlebusch-etal,
author = {Enno Ohlebusch and Mohamed I. Abouelhoda and Kathrin Hockel and
Jan Stallkamp},
title = {{The Median Problem for the Reversal Distance in Circular Bacterial
Genomes}},
booktitle = {{Proceedings of the 16th Annual Symposium on Combinatorial
Pattern Matching (CPM'2005)}},
year = {2005},
pages = {116--127},
publisher = {{Springer Berlin Heidelberg}},
address = {Heidelberg, Germany},
series = {{Lecture Notes in Computer Science}},
editor = {A. Apostolico and M. Crochemore and K. Park},
volume = {3537}
}
@inproceedings{2005-goldstein-etal,
author = {Avraham Goldstein and Petr Kolman and Jie Zheng},
editor = {R. Fleischer and G. Trippen},
title = {{Minimum Common String Partition Problem: Hardness and
Approximations}},
booktitle = {{Proceedings of the 15th International Symposium on Algorithms
and Computation (ISAAC'2004)}},
year = {2005},
publisher = {Springer Berlin Heidelberg},
address = {Berlin, Heidelberg},
pages = {484--495}
}
@article{2005-chen-etal,
author = {Xin Chen and Jie Zheng and Zheng Fu and Peng Nan and Yang Zhong
and Stefano Lonardi and Tao Jiang},
title = {{Assignment of Orthologous Genes via Genome Rearrangement}},
journal = {{IEEE/ACM Transactions on Computational Biology and
Bioinformatics}},
volume = {2},
number = {4},
year = {2005},
pages = {302--315},
publisher = {IEEE Computer Society Press},
address = {Los Alamitos, CA, USA}
}
@article{2006-elias-hartman,
author = {Isaac Elias and Tzvika Hartman},
title = {{A 1.375-Approximation Algorithm for Sorting by Transpositions}},
journal = {{IEEE/ACM Transactions on Computational Biology and
Bioinformatics}},
volume = {3},
number = {4},
year = {2006},
pages = {369--379}
}
@article{2006-labarre,
author = {Anthony Labarre},
title = {{New Bounds and Tractable Instances for the Transposition
Distance}},
journal = {{IEEE/ACM Transactions on Computational Biology and
Bioinformatics}},
volume = {3},
number = {4},
year = {2006},
pages = {380--394}
}
@article{2006-bernt-etal,
author = {Matthias Bernt and Daniel Merkle and Martin Middendorf},
title = {{Genome Rearrangement Based on Reversals that Preserve Conserved
Intervals}},
journal = {{IEEE/ACM Transactions on Computational Biology and
Bioinformatics}},
volume = {3},
number = {3},
year = {2006},
pages = {275--288}
}
@article{2006-hartman-shamir,
author = {Tzvika Hartman and Ron Shamir},
journal = {{Journal Information and Computation}},
number = {2},
pages = {275--290},
title = {{A Simpler and Faster 1.5-approximation Algorithm for Sorting by
Transpositions}},
volume = {204},
year = {2006}
}
@inproceedings{2006-han,
title = {{Improving the Efficiency of Sorting by Reversals}},
author = {Yijie Han},
booktitle = {{Proceedings of the 2006 International Conference on
Bioinformatics \& Computational Biology (BIOCOMP'2006)}},
year = {2006},
pages = {635--646},
publisher = {{CSREA Press}},
editor = {H. R. Arabnia and H. Valafar}
}
@article{2006-kaplan-shafir,
title = {{The Greedy Algorithm for Edit Distance with Moves}},
author = {Haim Kaplan and Nira Shafrir},
journal = {{Information Processing Letters}},
volume = {97},
number = {1},
pages = {23--27},
year = {2006},
publisher = {Elsevier}
}
@article{2007-hurkens-etal,
author = {Cor Hurkens and Leo van Iersel and Judith Keijsper and Steven Kelk
and Leen Stougie and John Tromp},
title = {{Prefix Reversals on Binary and Ternary Strings}},
journal = {{SIAM Journal on Discrete Mathematics}},
volume = {21},
number = {3},
pages = {592--611},
year = {2007}
}
@article{2007-bader-ohlebusch,
title = {{Sorting by Weighted Reversals, Transpositions, and Inverted
Transpositions}},
author = {Martin Bader and Enno Ohlebusch},
year = {2007},
journal = {{Journal of Computational Biology}},
volume = {14},
number = {5},
pages = {615--636}
}
@phdthesis{2007-mira,
author = {Cleber V. G. Mira},
school = {{Institute of Computing, University of Campinas}},
title = {{An{\'a}lise Alg{\'e}brica de Rearranjo em Genomas -- Algoritmos e
Complexidade}},
note = {{In Portuguese}},
year = {2007}
}
@article{2007-tannier-etal,
author = {Eric Tannier and Anne Bergeron and Marie-France Sagot},
title = {{Advances on Sorting by Reversals}},
journal = {{Discrete Applied Mathematics}},
volume = {155},
number = {6-7},
year = {2007},
pages = {881--888}
}
@article{2007-berard-etal,
author = {S{\` e}verine B{\' e}rard and Anne Bergeron and Cedric Chauve and
Christophe Paul},
journal = {{IEEE/ACM Transactions on Computational Biology and
Bioinformatics}},
title = {{Perfect Sorting by Reversals is not Always Difficult}},
year = {2007},
volume = {4},
number = {1},
pages = {4--16}
}
@article{2007-cranston-etal,
title = {{Short Proofs for Cut-and-Paste Sorting of Permutations}},
author = {Daniel W. Cranston and Ivan H. Sudborough and Douglas B. West},
journal = {{Discrete Mathematics}},
volume = {307},
number = {22},
pages = {2866--2870},
year = {2007}
}
@inproceedings{2007-gagne-hamel,
author = {Maxime Beno\^{\i}t-Gagn{\'e} and Sylvie Hamel},
title = {{A New and Faster Method of Sorting by Transpositions}},
booktitle = {{Proceedings of the 18th Annual Conference on Combinatorial
Pattern Matching (CPM'2007)}},
pages = {131--141},
publisher = {{Springer Berlin Heidelberg}},
address = {Heidelberg, Germany},
year = {2007},
series = {{Lecture Notes in Computer Science}},
editor = {B. Ma and Kaizhong Zhang},
volume = {4580}
}
@article{2007-feng-zhu,
author = {J. Feng and D. Zhu},
journal = {{ACM Transactions on Algorithms}},
number = {3},
pages = {25},
title = {{Faster Algorithms for Sorting by Transpositions and Sorting by
Block Interchanges}},
volume = {3},
year = {2007}
}
@inproceedings{2007-dias-souza,
address = {Angra dos Reis, Brasil},
author = {Zanoni Dias and Cid C. de Souza},
booktitle = {{Proceedings of the 3rd Brazilian Symposium on Bioinformatics
(BSB'2007)}},
pages = {74--85},
title = {{Polynomial-sized ILP Models for Rearrangement Distance Problems}},
year = {2007},
editor = {M.-F. Sagot and M. E. M. T. Walter}
}
@article{2007a-kolman-walen,
title = {{Approximating Reversal Distance for Strings with Bounded Number of
Duplicates}},
journal = {{Discrete Applied Mathematics}},
volume = {155},
number = {3},
pages = {327--336},
year = {2007},
author = {Petr Kolman and Tomasz Wale\'{n}}
}
@inproceedings{2007b-kolman-walen,
author = {Petr Kolman and Tomasz Wale\'{n}},
editor = {T. Erlebach and C. Kaklamanis},
title = {{Reversal Distance for Strings with Duplicates: Linear Time
Approximation Using Hitting Set}},
booktitle = {{Proceedings of the 4th International Workshop on Approximation
and Online Algorithms (WAOA'2006)}},
year = {2007},
publisher = {Springer Berlin Heidelberg},
address = {Berlin, Heidelberg},
pages = {279--289}
}
@inproceedings{2007-he,
author = {Dan He},
editor = {I. M{\u{a}}ndoiu and A. Zelikovsky},
title = {{A Novel Greedy Algorithm for the Minimum Common String Partition
Problem}},
booktitle = {{Proceedings on the 3rd International Symposium on
Bioinformatics Research and Applications (ISBRA'2007)}},
year = {2007},
publisher = {Springer Berlin Heidelberg},
address = {Berlin, Heidelberg},
pages = {441--452}
}
@article{2008-rahman-etal,
author = {Atif Rahman and Swakkhar Shatabda and Masud Hasan},
title = {{An Approximation Algorithm for Sorting by Reversals and
Transpositions}},
journal = {{Journal of Discrete Algorithms}},
volume = {6},
number = {3},
year = {2008},
pages = {449--457}
}
@article{2008-haynes-etal,
author = {Karmella A. Haynes and Marian L. Broderick and Adam D. Brown and
Trevor L. Butner and James O. Dickson and W. L. Harden and Lane H.
Heard and Eric L. Jessen and Kelly J. Malloy and Brad J. Ogden and
Sabriya Rosemond and Samantha Simpson and Erin Zwack and A. M.
Campbell and Todd T. Eckdahl and Laurie J. Heyer and Jeffrey L.
Poet},
title = {{Engineering Bacteria to Solve the Burnt Pancake Problem}},
journal = {{Journal of Biological Engineering}},
pages = {1--12},
volume = {2},
year = {2008},
number = {}
}
@inproceedings{2008-labarre,
author = {Anthony Labarre},
title = {{Edit Distances and Factorisations of Even Permutations}},
booktitle = {{Proceedings of the 16th Annual European Symposium on Algorithms
(ESA'2008)}},
year = {2008},
pages = {635--646},
publisher = {{Springer-Verlag}},
address = {Berlin, Heidelberg},
series = {{Lecture Notes in Computer Science}},
editor = {D. Halperin and K. Mehlhorn},
volume = {5193}
}
@article{2008-bader-etal,
title = {{A Fast Algorithm for the Multiple Genome Rearrangement Problem with
Weighted Reversals and Transpositions}},
author = {Martin Bader and Mohamed I. Abouelhoda and Enno Ohlebusch},
year = {2008},
journal = {{BMC Bioinformatics}},
volume = {9},
number = {1},
pages = {1--13}
}
@article{2008-bender-etal,
author = {Michael A. Bender and Dongdong Ge and Simai He and Haodong Hu and
Ron Y. Pinter and Steven S. Skiena and Firas Swidan},
title = {{Improved Bounds on Sorting by Length-Weighted Reversals}},
journal = {{Journal of Computer and System Sciences}},
volume = {74},
number = {5},
year = {2008},
pages = {744--774}
}
@article{2008-konstantinova,
author = {Elena Konstantinova},
title = {{Some Problems on Cayley Graphs}},
journal = {{Linear Algebra and its Applications}},
volume = {429},
number = {11-12},
pages = {2754--2769},
year = {2008}
}
@inproceedings{2008-hausen-etal,
author = {Rodrigo A. Hausen and Luerbio Faria and Celina M. H. Figueiredo
and Luis A. B. Kowada},
booktitle = {{Proceedings of the 3rd Brazilian Symposium on Bioinformatics
(BSB'2008)}},
pages = {79--91},
title = {{On the Toric Graph as a Tool to Handle the Problem of Sorting by
Transpositions}},
publisher = {{Springer Berlin Heidelberg}},
address = {Heidelberg, Germany},
year = {2008},
series = {{Lecture Notes in Computer Science}},
editor = {A. L. C. Bazzan and M. Craven and N. F. Martins},
volume = {5167}
}
@inproceedings{2008-mira-etal,
author = {Cleber V. G. Mira and Zanoni Dias and Hederson P. Santos and
Guilherme A. Pinto and Maria E. M. T. Walter},
booktitle = {{Proceedings of the 3rd Brazilian Symposium on Bioinformatics
(BSB'2008)}},
pages = {115--126},
title = {{Transposition Distance Based on the Algebraic Formalism}},
publisher = {{Springer Berlin Heidelberg}},
address = {Heidelberg, Germany},
year = {2008},
series = {{Lecture Notes in Computer Science}},
editor = {A. L. C. Bazzan and M. Craven and N. F. Martins},
volume = {5167}
}
@article{2008-darling-etal,
author = {Aaron E. Darling and Istv{\'a}n Mikl{\'o}s and Mark A. Ragan},
journal = {{PLoS Genetics}},
number = {7},
pages = {{e1000128}},
title = {{Dynamics of Genome Rearrangement in Bacterial Populations}},
volume = {4},
year = {2008}
}
@article{2009-chitturi-etal,
author = {Bhadrachalam Chitturi and William Fahle and Z. Meng and Linda
Morales and Charles O. Shields and Ivan H. Sudborough and Walter
Voit},
title = {{An (18/11)n Upper Bound for Sorting by Prefix Reversals}},
journal = {{Theoretical Computer Science}},
volume = {410},
number = {36},
year = {2009},
pages = {3372--3390}
}
@book{2009-fertin-etal,
title = {{Combinatorics of Genome Rearrangements}},
author = {Guillaume Fertin and Anthony Labarre and Irena Rusu and {\'E}ric
Tannier and St{\'e}phane Vialette},
series = {{Computational Molecular Biology}},
year = {2009},
publisher = {{The MIT Press}},
address = {London, England}
}
@book{2009-cormen-etal,
title = {{Introduction to Algorithms}},
year = {2009},
publisher = {{The MIT Press}},
address = {London, England},
pages = {288},
author = {Thomas H. Cormen and Charles E. Leiserson and Ronald L. Rivest and
Clifford Stein},
edition = {3rd}
}
@article{2009-lin-etal,
author = {Ying C. Lin and Chun-Yuan Lin and Chunhung R. Lin},
title = {{Sorting by Reversals and Block-Interchanges with Various Weight
Assignments}},
journal = {{BMC Bioinformatics}},
volume = {10},
year = {2009},
number = {1},
pages = {398}
}
@incollection{2009-dias-dias,
author = {Ulisses Dias and Zanoni Dias},
booktitle = {{Proceedings of the 4th Brazilian Symposium on Bioinformatics
(BSB'2009)}},
pages = {13--23},
series = {{Lecture Notes in Computer Science}},
title = {{Constraint Programming Models for Transposition Distance Problem}},
volume = {5676},
publisher = {{Springer Berlin Heidelberg}},
address = {Heidelberg, Germany},
year = {2009}
}
@phdthesis{2010-baudet,
author = {Christian Baudet},
school = {{Institute of Computing, University of Campinas}},
title = {{Enumera{\c c}{\~a}o de Traces e Identifica{\c c}{\~a}o de
Breakpoints: Estudo de Aspectos da Evolu{\c c}{\~a}o}},
note = {{In Portuguese}},
year = {2010}
}
@article{2010-sharmin-etal,
author = {Mahfuza Sharmin and Rukhsana Yeasmin and Masud Hasan and Atif
Rahman and Mohammad S. Rahman},
title = {{Pancake Flipping with Two Spatulas}},
journal = {{Electronic Notes in Discrete Mathematics}},
volume = {36},
pages = {231--238},
year = {2010},
number = {}
}
@inproceedings{2010-williams,
author = {Aaron Williams},
title = {{O(1)-Time Unsorting by Prefix-Reversals in a Boustrophedon Linked
List}},
booktitle = {{Proceedings of the 5th International Conference on Fun with
Algorithms (FUN'2010)}},
year = {2010},
pages = {368--379},
publisher = {{Springer-Verlag}},
address = {{Berlin, Heidelberg}},
series = {{Lecture Notes in Computer Science}},
editor = {P. Boldi and L. Gargano},
volume = {6099}
}
@inproceedings{2010-helmert,
author = {Malte Helmert},
title = {{Landmark Heuristics for the Pancake Problem}},
booktitle = {{Proceedings of the 3rd Annual Symposium on Combinatorial Search
(SOCS'2010)}},
publisher = {{AAAI Press}},
pages = {109--110},
year = {2010},
editor = {N. Sturtevant and A. Felner}
}
@article{2010-lou-zhu,
author = {Xiao-Wen Lou and Da-Ming Zhu},
title = {{Sorting Unsigned Permutations by Weighted Reversals,
Transpositions, and Transreversals}},
year = {2010},
journal = {{Journal of Computer Science and Technology}},
volume = {25},
number = {4},
pages = {853--863}
}
@incollection{2010a-swenson-etal,
title = {{Listing All Sorting Reversals in Quadratic Time}},
author = {Krister M. Swenson and Ghada Badr and David Sankoff},
booktitle = {{Algorithms in Bioinformatics}},
year = {2010},
volume = {6293},
series = {{Lecture Notes in Computer Science}},
editor = {V. Moulton and M. Singh},
publisher = {{Springer Berlin Heidelberg}},
address = {Heidelberg, Germany},
pages = {102--110}
}
@article{2010b-swenson-etal,
author = {Krister M. Swenson and Vaibhav Rajan and Yu Lin and Bernard M. E. Moret},
title = {{Sorting Signed Permutations by Inversions in ${O}(n \log n)$ time}},
journal = {{Journal of Computational Biology}},
volume = {17},
number = {3},
year = {2010},
pages = {489--501}
}
@article{2010-alam-etal,
author = {Mohammad T. Alam and Maria E. Merlo and Eriko Takano and Rainer
Breitling},
journal = {{Molecular Phylogenetics and Evolution}},
pages = {763--772},
title = {{Genome-based Phylogenetic Analysis of Streptomyces and its
Relatives}},
volume = {54},
year = {2010}
}
@misc{2010a-dias-dias,
author = {Ulisses Dias and Zanoni Dias},
title = {{(4,3)-Sequences for two Oriented Cycles that do not Lead to a
Valid 2-move}},
year = {2010},
howpublished = {\url{http://www.ic.unicamp.br/~udias/DD2010a/proof1/index.html}}
}
@misc{2010b-dias-dias,
author = {Ulisses Dias and Zanoni Dias},
howpublished = {\url{http://www.ic.unicamp.br/~zanoni/sib}},
title = {{SIB - Symmetric Inversion in Bacteria}},
year = {2010}
}
@inproceedings{2010c-dias-dias,
author = {Ulisses Dias and Zanoni Dias},
booktitle = {{Proceedings of the 1st International Symposium on Biocomputing
(ISB'2010)}},
pages = {1--8},
title = {{Extending Bafna-Pevzner Algorithm}},
year = {2010},
publisher = {ACM},
address = {New York, NY, USA}
}
@inproceedings{2010d-dias-dias,
author = {Ulisses Dias and Zanoni Dias},
booktitle = {{Proceeding of the 1st ACM International Conference on
Bioinformatics and Computational Biology (BCB'2010)}},
pages = {334--337},
publisher = {{ACM}},
address = {New York, NY, USA},
title = {{An Improved $1.375$-approximation Algorithm for the Transposition
Distance Problem}},
year = {2010}
}
@article{2011-cibulka,
author = {Josef Cibulka},
title = {{On Average and Highest Number of Flips in Pancake Sorting}},
journal = {{Theoretical Computer Science}},
volume = {412},
number = {8-10},
year = {2011},
pages = {822--834}
}
@article{2011-labarre-cibulka,
author = {Anthony Labarre and Josef Cibulka},
title = {{Polynomial-Time Sortable Stacks of Burnt Pancakes}},
journal = {{Theoretical Computer Science}},
volume = {412},
number = {8-10},
year = {2011},
pages = {695--702}
}
@inproceedings{2011a-galvao-dias,
author = {Gustavo R. Galv{\~a}o and Zanoni Dias},
title = {{Computing Rearrangement Distance of Every Permutation in the
Symmetric Group}},
booktitle = {{Proceedings of the 26th ACM Symposium on Applied Computing
(SAC'2011)}},
year = {2011},
pages = {106--107},
editor = {W. C. Chu and W. E. Wong and M. J. Palakal and C.-C. Hung},
publisher = {{ACM}},
address = {New York, NY, USA}
}
@misc{2011b-galvao-dias,
author = {Gustavo R. Galv{\~a}o and Zanoni Dias},
howpublished = {\url{http://mirza.ic.unicamp.br:8080}},
title = {{Rearrangement Distance Database and Genome Rearrangement Algorithm
Auditor (GRAAu)}},
year = {2011}
}
@inproceedings{2011a-dias-etal,
author = {Ulisses Dias and Zanoni Dias and Jo{\~a} C. Setubal},
booktitle = {{Proceedings of the 6th Brazilian Symposium on Bioinformatics
(BSB'2011)}},
pages = {73--76},
title = {{Evaluation of Genome Distance Measures using Tree-derived
Distances}},
year = {2011},
editor = {O. N. de Souza G. P. Telles and M. J. Palakal}
}
@inproceedings{2011c-galvao-dias,
author = {Gustavo R. Galv{\~a}o and Zanoni Dias},
title = {{On the Distribution of Rearrangement Distances}},
booktitle = {{Proceedings of the 6th Brazilian Symposium on Bioinformatics
(BSB'2011)}},
year = {2011},
pages = {41--48},
editor = {O. N. de Souza G. P. Telles and M. J. Palakal}
}
@inproceedings{2011b-dias-etal,
author = {Ulisses Dias and Zanoni Dias and Jo{\~a} C. Setubal},
booktitle = {{Proceedings of the 6th Brazilian Symposium on Bioinformatics
(BSB'2011)}},
pages = {61--64},
title = {{Two New Whole-genome Distance Measures}},
year = {2011},
editor = {O. N. de Souza G. P. Telles and M. J. Palakal}
}
@inproceedings{2011c-dias-etal,
author = {Ulisses Dias and Zanoni Dias and Jo{\~a} C. Setubal},
booktitle = {{Proceeding of the 2nd ACM International Conference on
Bioinformatics and Computational Biology (BCB'2011)}},
pages = {39--48},
title = {{Using Inversion Signatures to Generate Draft Genome Sequence
Scaffolds}},
year = {2011},
publisher = {{ACM}},
address = {New York, NY, USA}
}
@incollection{2011d-dias-etal,
author = {Ulisses Dias and Zanoni Dias and Jo{\~a} C. Setubal},
booktitle = {{Comparative Genomics}},
pages = {240--251},
series = {{Lecture Notes in Computer Science}},
title = {{A Simulation Tool for the Study of Symmetric Inversions in
Bacterial Genomes}},
volume = {6398},
year = {2011},
publisher = {{Springer-Verlag}},
address = {Berlin, Germany}
}
@article{2012-bulteau-etal,
author = {Laurent Bulteau and Guillaume Fertin and Irena Rusu},
title = {{Sorting by Transpositions is Difficult}},
journal = {{SIAM Journal on Computing}},
year = {2012},
number = {3},
volume = {26},
pages = {1148--1180}
}
@article{2012-chitturi-sudborough,
title = {{Bounding Prefix Transposition Distance for Strings and
Permutations}},
author = {Bhadrachalam Chitturi and Ivan H. Sudborough},
journal = {{Theoretical Computer Science}},
volume = {421},
pages = {15--24},
year = {2012},
number = {}
}
@phdthesis{2012-dias,
author = {Ulisses Martins Dias},
school = {{Institute of Computing, University of Campinas}},
title = {{Problemas de Compara{\c c}{\~a}o de Genomas}},
note = {{In Portuguese}},
year = {2012}
}
@mastersthesis{2012-galvao,
author = {Gustavo Rodrigues Galv{\~a}o},
title = {{Uma Ferramenta de Auditoria para Algoritmos de Rearranjo de
Genomas}},
school = {Institute of Computing, University of Campinas},
year = {2012},
note = {{In Portuguese}}
}
@inproceedings{2012-dias-etal,
author = {Zanoni Dias and Ulisses Dias and Lenwood S. Heath and Jo\~{a}o C.
Setubal},
title = {{Sorting Genomes Using Almost-Symmetric Inversions}},
booktitle = {{Proceedings of the 27th Annual ACM Symposium on Applied
Computing (SAC'2012)}},
year = {2012},
pages = {1368--1374},
publisher = {ACM},
address = {New York, NY, USA}
}
@inproceedings{2012a-galvao-dias,
author = {Gustavo R. Galv{\~a}o and Zanoni Dias},
title = {{On the Performance of Sorting Permutations by Prefix Operations}},
booktitle = {{Proceedings of the 4th International Conference on
Bioinformatics and Computational Biology (BICoB'2012)}},
year = {2012},
pages = {102--107},
editor = {F. Saeed},
publisher = {International Society for Computers and their Applications}
}
@inproceedings{2012b-galvao-dias,
author = {Gustavo R. Galv{\~a}o and Zanoni Dias},
title = {{GRAAu: Genome Rearrangement Algorithm Auditor}},
booktitle = {{Proceedings of the 4th International Conference on
Bioinformatics and Computational Biology (BICoB'2012)}},
year = {2012},
pages = {97--101},
editor = {F. Saeed},
publisher = {International Society for Computers and their Applications}
}
@article{2012a-jiang-etal,
author = {Haitao Jiang and Binhai Zhu and Daming Zhu Hong Zhu},
title = {{Minimum Common String Partition Revisited}},
journal = {{Journal of Combinatorial Optimization}},
year = {2012},
volume = {23},
number = {4},
pages = {519--527}
}
@article{2012b-jiang-etal,
title = {{A (1+e)-Approximation Algorithm for Sorting by Short Block-Moves}},
author = {Haitao Jiang and Daming Zhu and Binhai Zhu},
journal = {{Theoretical Computer Science}},
volume = {437},
pages = {1--8},
year = {2012}
}
@article{2013-chen,
author = {Xin Chen},
title = {{On Sorting Unsigned Permutations by Double-Cut-and-Joins}},
journal = {{Journal of Combinatorial Optimization}},
volume = {25},
number = {3},
year = {2013},
pages = {339--351}
}
@incollection{2013-cunha-etal,
author = {Lu{\' i}s F. I. Cunha and Luis A. B. Kowada and Rodrigo de A.
Hausen and Celina M. H. de Figueiredo},
title = {{On the 1.375-Approximation Algorithm for Sorting by Transpositions
in O(n log n) Time}},
editor = {J. C. Setubal and N. F. Almeida},
year = {2013},
booktitle = {{Advances in Bioinformatics and Computational Biology}},
volume = {8213},
series = {{Lecture Notes in Computer Science}},
publisher = {{Springer International Publishing}},
pages = {126--135},
address = {Switzerland}
}
@inproceedings{2013-arruda-etal,
author = {Thiago da S. Arruda and Ulisses Dias and Zanoni Dias},
title = {{Heuristics for the Sorting by Length-Weighted Inversion Problem}},
booktitle = {{Proceedings of the 4th International Conference on Bioinformatics,
Computational Biology and Biomedical Informatics (BCB'2013)}},
year = {2013},
pages = {498:498--498:507},
publisher = {ACM},
address = {New York, NY, USA},
series = {{Lecture Notes in Computer Science}},
editor = {A.-H. Dediu and C. Mart{\'i}n-Vide and B. Truthe},
volume = {8542}
}
@article{2013-dutta-etal,
author = {Amit K. Dutta and Masud Hasan and Mohammad S. Rahman},
title = {{Prefix Transpositions on Binary and Ternary Strings}},
journal = {{Information Processing Letters}},
volume = {113},
number = {8},
pages = {265--270},
year = {2013}
}
@article{2013a-dias-dias,
title = {{Heuristics for the Transposition Distance Problem}},
author = {Ulisses Dias and Zanoni Dias},
journal = {{Journal of Bioinformatics and Computational Biology}},
volume = {11},
number = {5},
pages = {17},
year = {2013}
}
@inproceedings{2013-dias-etal,
author = {Ulisses Dias and Christian Baudet and Zanoni Dias},
title = {{Greedy Randomized Search Procedure to Sort Genomes Using
Symmetric, Almost-Symmetric and Unitary Inversions}},
booktitle = {{Proceedings of the 4th International Conference on Bioinformatics,
Computational Biology and Biomedical Informatics (BCB'2013)}},
year = {2013},
pages = {181--190},
publisher = {ACM},
address = {New York, NY, USA},
series = {{Lecture Notes in Computer Science}},
editor = {A.-H. Dediu and C. Mart{\'i}n-Vide and B. Truthe},
volume = {8542}
}
@inproceedings{2013b-dias-dias,
author = {Ulisses Dias and Zanoni Dias},
booktitle = {{Proceedings of the 5th International Conference on
Bioinformatics and Computational Biology (BICoB'2013)}},
pages = {261--268},
title = {{Sorting Genomes using Symmetric, Almost-symmetric and Unitary
Inversions}},
year = {2013}
}
@incollection{2014a-lintzmayer-dias,
author = {Carla N. Lintzmayer and Zanoni Dias},
title = {{Sorting Permutations by Prefix and Suffix Versions of Reversals and
Transpositions}},
year = {2014},
booktitle = {{LATIN 2014: Theoretical Informatics}},
volume = {8392},
series = {{Lecture Notes in Computer Science}},
editor = {A. Pardo and A. Viola},
publisher = {{Springer Berlin Heidelberg}},
address = {Heidelberg, Germany},
pages = {671--682}
}
@incollection{2014b-lintzmayer-dias,
author = {Carla N. Lintzmayer and Zanoni Dias},
title = {{On Sorting of Signed Permutations by Prefix and Suffix Reversals
and Transpositions}},
year = {2014},
booktitle = {{Algorithms for Computational Biology}},
volume = {8542},
series = {{Lecture Notes in Computer Science}},
editor = {A.-H. Dediu and C. Mart{\' i}n-Vide and B. Truthe},
publisher = {{Springer International Publishing}},
address = {Switzerland},
pages = {146--157}
}
@incollection{2014c-lintzmayer-dias,
author = {Carla N. Lintzmayer and Zanoni Dias},
title = {{On the Diameter of Rearrangement Problems}},
year = {2014},
booktitle = {{Algorithms for Computational Biology}},
volume = {8542},
series = {{Lecture Notes in Computer Science}},
editor = {A.-H. Dediu and C. Mart{\' i}n-Vide and B. Truthe},
publisher = {{Springer International Publishing}},
address = {Switzerland},
pages = {158--170}
}
@incollection{2014-arruda-etal,
author = {Thiago da S. Arruda and Ulisses Dias and Zanoni Dias},
title = {{Heuristics for the Sorting by Length-Weighted Inversions Problem
on Signed Permutations}},
year = {2014},
booktitle = {{Algorithms for Computational Biology}},
volume = {8542},
series = {{Lecture Notes in Computer Science}},
editor = {A.-H. Dediu and C. Mart{\' i}n-Vide and B. Truthe},
publisher = {{Springer International Publishing}},
address = {Switzerland},
pages = {59--70}
}
@incollection{2014-baudet-etal,
author = {Christian Baudet and Ulisses Dias and Zanoni Dias},
title = {{Length and Symmetry on the Sorting by Weighted Inversions
Problem}},
year = {2014},
booktitle = {{Advances in Bioinformatics and Computational Biology}},
volume = {8826},
series = {{Lecture Notes in Computer Science}},
editor = {S. Campos},
publisher = {{Springer International Publishing}},
address = {Switzerland},
pages = {99--106}
}
@incollection{2014-bulteau-etal,
author = {Laurent Bulteau and Guillaume Fertin and Christian Komusiewicz},
title = {{Reversal Distances for Strings with Few Blocks or Small Alphabets}},
year = {2014},
booktitle = {{Combinatorial Pattern Matching}},
volume = {8486},
series = {{Lecture Notes in Computer Science}},
editor = {A. S. Kulikov and S. O. Kuznetsov and P. A. Pevzner},
publisher = {{Springer International Publishing}},
address = {Switzerland},
pages = {50--59}
}
@article{2014a-dias-etal,
title = {{A General Heuristic for Genome Rearrangement Problems}},
author = {Ulisses Dias and Gustavo R. Galv{\~a}o and Carla N. Lintzmayer
and Zanoni Dias},
journal = {{Journal of Bioinformatics and Computational Biology}},
volume = {12},
number = {3},
pages = {26},
year = {2014}
}
@unpublished{2014-zuylen-etal,
author = {Anke van Zuylen James Bieron and Frans Schalekamp and Gexin Yu},
title = {{An Upper Bound on the Number of Circular Transpositions to Sort a
Permutation}},
journal = {CoRR},
year = {2014},
note = {\url{http://arxiv.org/abs/1402.4867}}
}
@inproceedings{2014b-dias-etal,
author = {Ulisses Dias and Andre R. Oliveira and Zanoni Dias},
title = {{An Improved Algorithm for the Sorting by Reversals and
Transpositions Problem}},
booktitle = {{Proceedings of the 5th ACM Conference on Bioinformatics,
Computational Biology, and Health Informatics (BCB'2014)}},
year = {2014},
pages = {400--409},
publisher = {ACM},
address = {New York, NY, USA}
}
@article{2014-goldstein-lewenstein,
title = {{Quick Greedy Computation for Minimum Common String Partition}},
journal = {{Theoretical Computer Science}},
volume = {542},
pages = {98--107},
year = {2014},
author = {Isaac Goldstein and Moshe Lewenstein}
}
@inproceedings{2014-jiang-etal,
title = {{An 5/4-Approximation Algorithm for Sorting Permutations by Short Block Moves}},
author = {Haitao Jiang and Haodi Feng and Daming Zhu},
booktitle = {{Proceedings of the 25th International Symposium on Algorithms
and Computation (ISAAC'2014)}},
pages = {491--503},
year = {2014},
publisher = {{Springer International Publishing}},
series = {{Lecture Notes in Computer Science}},
editor = {H. Ahn and C. Shin}
}
@article{2014a-galvao-dias,
author = {Gustavo R. Galv{\~a}o and Zanoni Dias},
title = {{An Audit Tool for Genome Rearrangement Algorithms}},
journal = {{Journal of Experimental Algorithmics}},
volume = {19},
year = {2014},
pages = {1--34}
}
@inproceedings{2014b-galvao-dias,
title = {{Approximation Algorithms for Sorting by Signed Short Reversals}},
author = {Gustavo Rodrigues Galv{\~a}o and Zanoni Dias},
booktitle = {{Proceedings of the 5th ACM Conference on Bioinformatics,
Computational Biology, and Health Informatics (BCB'2014)}},
pages = {360--369},
year = {2014},
organization = {ACM},
address = {New York, NY, USA}
}
@article{2015-dias-dias,
title = {{Sorting by Prefix Reversals and Prefix Transpositions}},
author = {Zanoni Dias and Ulisses Dias},
journal = {{Discrete Applied Mathematics}},
volume = {181},
pages = {78--89},
year = {2015}
}
@article{2015a-galvao-etal,
author = {Gustavo R. Galv{\~a}o and Orlando Lee and Zanoni Dias},
title = {{Sorting Signed Permutations by Short Operations}},
year = {2015},
journal = {{Algorithms for Molecular Biology}},
volume = {10},
pages = {1--17},
number = {1}
}
@incollection{2015b-galvao-etal,
author = {Gustavo R. Galv{\~a}o and Christian Baudet and Zanoni Dias},
editor = {R. Harrison and Y. Li and I. M\u{a}ndoiu},
title = {{Sorting Signed Circular Permutations by Super Short Reversals}},
booktitle = {{Proceedings of the 11th International Symposium on
Bioinformatics Research and Applications (ISBRA'2015)}},
series = {{Lecture Notes in Computer Science}},
year = {2015},
publisher = {{Springer International Publishing}},
address = {Switzerland},
pages = {272--283}
}
@article{2015-rahman-rahman,
author = {Md. K. Rahman and Mohammad S. Rahman},
title = {{Prefix and Suffix Transreversals on Binary and Ternary Strings}},
journal = {{Journal of Discrete Algorithms}},
year = {2015},
volume = {33},
pages = {160--170}
}
@article{2015-hasan-etal,
title = {{Pancake Flipping and Sorting Permutations}},
journal = {{Journal of Discrete Algorithms}},
year = {2015},
author = {Masud Hasan and Atif Rahman and Md. K. Rahman and Mohammad S.
Rahman and Mahfuza Sharmin and Rukhsana Yeasmin},
volume = {33},
pages = {139--149}
}
@article{2015-lintzmayer-etal,
title = {{Approximation Algorithms for Sorting by Length-Weighted Prefix and
Suffix Operations}},
author = {Carla N. Lintzmayer and Guillaume Fertin and Zanoni Dias},
journal = {{Theoretical Computer Science}},
year = {2015},
volume = {593},
pages = {26--41}
}
@article{2015-bulteau-etal,
title = {{Pancake Flipping is Hard}},
journal = {{Journal of Computer and System Sciences}},
author = {Laurent Bulteau and Guillaume Fertin and Irena Rusu},
volume = {81},
number = {8},
pages = {1556--1574},
year = {2015}
}
@incollection{2015-fertin-etal,
title = {{Prefix and Suffix Reversals on Strings}},
author = {Guillaume Fertin and Lo\"{i}c Jankowiak and G\'{e}raldine Jean},
year = {2015},
booktitle = {{String Processing and Information Retrieval}},
volume = {9309},
series = {{Lecture Notes in Computer Science}},
editor = {C. Iliopoulos and S. Puglisi and E. Yilmaz},
publisher = {Springer International Publishing},
address = {Switzerland},
pages = {165--176}
}
@article{2015-chitturi,
title = {{Tighter Upper Bound for Sorting Permutations with Prefix Transpositions}},
author = {Bhadrachalam Chitturi},
journal = {{Theoretical Computer Science}},
year = {2015},
volume = {602},
pages = {22--31}
}
@unpublished{2015-rusu,
author = {Irena Rusu},
title = {{Log-Lists and Their Applications to Sorting by Transpositions,
Reversals and Block-Interchanges}},
journal = {CoRR},
year = {2015},
note = {\url{http://arxiv.org/abs/1507.01512}}
}
@article{2016-bulteau-etal,
title = {{(Prefix) Reversal Distance for (Signed) Strings with Few Blocks or
Small Alphabets}},
journal = {{Journal of Discrete Algorithms}},
volume = {37},
pages = {44--55},
year = {2016},
author = {Laurent Bulteau and Guillaume Fertin and Christian Komusiewicz}
}
@phdthesis{2016-lintzmayer,
author = {Carla Negri Lintzmayer},
title = {{The Problem of Sorting Permutations by Prefix and Suffix
Rearrangements}},
school = {{University of Campinas, Institute of Computing}},
year = {2016},
note = {{In English}}
}
@article{2017-lintzmayer-etal,
author = {Carla Negri Lintzmayer and Guillaume Fertin and Zanoni Dias},
title = {{Sorting Permutations by Prefix and Suffix Rearrangements}},
journal = {{Journal of Bioinformatics and Computational Biology}},
volume = {15},
number = {1},
pages = {1750002},
year = {2017}
}
This file was generated by bibtex2html 1.98.