TY - GEN
T1 - Rearrangement models and single-cut operations
AU - Medvedev, Paul
AU - Stoye, Jens
PY - 2009
Y1 - 2009
N2 - There have been many widely used genome rearrangement models, such as reversals, Hannenhalli-Pevzner, and double-cut and join. Though each one can be precisely defined, the general notion of a model remains undefined. In this paper, we give a formal set-theoretic definition, which allows us to investigate and prove relationships between distances under various existing and new models. We also initiate the formal study of single-cut operations by giving a linear time algorithm for the distance problem under a new single-cut and join model.
AB - There have been many widely used genome rearrangement models, such as reversals, Hannenhalli-Pevzner, and double-cut and join. Though each one can be precisely defined, the general notion of a model remains undefined. In this paper, we give a formal set-theoretic definition, which allows us to investigate and prove relationships between distances under various existing and new models. We also initiate the formal study of single-cut operations by giving a linear time algorithm for the distance problem under a new single-cut and join model.
UR - http://www.scopus.com/inward/record.url?scp=78651252771&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=78651252771&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-04744-2_8
DO - 10.1007/978-3-642-04744-2_8
M3 - Conference contribution
AN - SCOPUS:78651252771
SN - 3642047432
SN - 9783642047435
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 84
EP - 97
BT - Comparative Genomics - International Workshop, RECOMB-CG 2009, Proceedings
T2 - 7th International Workshop on Comparative Genomics, RECOMB-CG 2009
Y2 - 27 September 2009 through 29 September 2009
ER -