New bounds and tractable instances for the transposition distance. Labarre, A. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 3(4):380-394, Published by the IEEE CS, CI, and EMB Societies & the ACM, 10, 2006.
![New bounds and tractable instances for the transposition distance [pdf]](https://bibbase.org/img/filetypes/pdf.svg "pdf")
Paper ![New bounds and tractable instances for the transposition distance [link]](https://bibbase.org/img/filetypes/link.svg "link")
Website abstract bibtex
Paper Website abstract bibtex The problem of sorting by transpositions asks for a sequence of adjacent interval exchanges that sorts a permutation and is of the shortest possible length. The distance of the permutation is defined as the length of such a sequence. Despite the apparently intuitive nature of this problem, introduced in 1995 by Bafna and Pevzner, the complexity of both finding an optimal sequence and computing the distance remains open today. In this paper, we establish connections between two different graph representations of permutations, which allows us to compute the distance of a few non-trivial classes of permutations in linear time and space, bypassing the use of any graph structure. By showing that every permutation can be obtained from one of these classes, we prove a new tight upper bound on the transposition distance. Finally, we give improved bounds on some other families of permutations and prove formulas for computing the exact distance of other classes of permutations, again in polynomial time.
@article{
title = {New bounds and tractable instances for the transposition distance},
type = {article},
year = {2006},
identifiers = {[object Object]},
keywords = {Algorithms,Chromosome Mapping,Chromosome Mapping: methods,DNA,DNA Mutational Analysis,DNA Mutational Analysis: methods,DNA Transposable Elements,DNA Transposable Elements: genetics,DNA: methods,Evolution,Linkage Disequilibrium,Linkage Disequilibrium: genetics,Molecular,Sequence Alignment,Sequence Alignment: methods,Sequence Analysis},
pages = {380-394},
volume = {3},
websites = {http://www.ncbi.nlm.nih.gov/pubmed/17085847,http://www.computer.org/portal/web/csdl/doi/10.1109/tcbb.2006.56},
month = {10},
publisher = {Published by the IEEE CS, CI, and EMB Societies & the ACM},
city = {Los Alamitos, CA, USA},
id = {87436cd8-5b57-349e-bd20-d831b9b9a415},
created = {2009-09-25T17:31:36.000Z},
accessed = {2011-06-07},
file_attached = {true},
profile_id = {192e9f37-d4de-3f1f-95dc-8b4ae5980aa4},
last_modified = {2013-04-22T09:24:01.000Z},
tags = {genome rearrangements,sorting by transpositions},
read = {true},
starred = {false},
authored = {true},
confirmed = {true},
hidden = {false},
citation_key = {Labarre2006},
source_type = {article},
abstract = {The problem of sorting by transpositions asks for a sequence of adjacent interval exchanges that sorts a permutation and is of the shortest possible length. The distance of the permutation is defined as the length of such a sequence. Despite the apparently intuitive nature of this problem, introduced in 1995 by Bafna and Pevzner, the complexity of both finding an optimal sequence and computing the distance remains open today. In this paper, we establish connections between two different graph representations of permutations, which allows us to compute the distance of a few non-trivial classes of permutations in linear time and space, bypassing the use of any graph structure. By showing that every permutation can be obtained from one of these classes, we prove a new tight upper bound on the transposition distance. Finally, we give improved bounds on some other families of permutations and prove formulas for computing the exact distance of other classes of permutations, again in polynomial time.},
bibtype = {article},
author = {Labarre, Anthony},
journal = {IEEE/ACM Transactions on Computational Biology and Bioinformatics},
number = {4}
}Downloads: 0
{"_id":"6rKfRGZjjShiApyW8","bibbaseid":"labarre-newboundsandtractableinstancesforthetranspositiondistance-2006","downloads":0,"creationDate":"2016-03-04T08:38:10.583Z","title":"New bounds and tractable instances for the transposition distance","author_short":["Labarre, A."],"year":2006,"bibtype":"article","biburl":null,"bibdata":{"title":"New bounds and tractable instances for the transposition distance","type":"article","year":"2006","identifiers":"[object Object]","keywords":"Algorithms,Chromosome Mapping,Chromosome Mapping: methods,DNA,DNA Mutational Analysis,DNA Mutational Analysis: methods,DNA Transposable Elements,DNA Transposable Elements: genetics,DNA: methods,Evolution,Linkage Disequilibrium,Linkage Disequilibrium: genetics,Molecular,Sequence Alignment,Sequence Alignment: methods,Sequence Analysis","pages":"380-394","volume":"3","websites":"http://www.ncbi.nlm.nih.gov/pubmed/17085847,http://www.computer.org/portal/web/csdl/doi/10.1109/tcbb.2006.56","month":"10","publisher":"Published by the IEEE CS, CI, and EMB Societies & the ACM","city":"Los Alamitos, CA, USA","id":"87436cd8-5b57-349e-bd20-d831b9b9a415","created":"2009-09-25T17:31:36.000Z","accessed":"2011-06-07","file_attached":"true","profile_id":"192e9f37-d4de-3f1f-95dc-8b4ae5980aa4","last_modified":"2013-04-22T09:24:01.000Z","tags":"genome rearrangements,sorting by transpositions","read":"true","starred":false,"authored":"true","confirmed":"true","hidden":false,"citation_key":"Labarre2006","source_type":"article","abstract":"The problem of sorting by transpositions asks for a sequence of adjacent interval exchanges that sorts a permutation and is of the shortest possible length. The distance of the permutation is defined as the length of such a sequence. Despite the apparently intuitive nature of this problem, introduced in 1995 by Bafna and Pevzner, the complexity of both finding an optimal sequence and computing the distance remains open today. In this paper, we establish connections between two different graph representations of permutations, which allows us to compute the distance of a few non-trivial classes of permutations in linear time and space, bypassing the use of any graph structure. By showing that every permutation can be obtained from one of these classes, we prove a new tight upper bound on the transposition distance. Finally, we give improved bounds on some other families of permutations and prove formulas for computing the exact distance of other classes of permutations, again in polynomial time.","bibtype":"article","author":"Labarre, Anthony","journal":"IEEE/ACM Transactions on Computational Biology and Bioinformatics","number":"4","bibtex":"@article{\n title = {New bounds and tractable instances for the transposition distance},\n type = {article},\n year = {2006},\n identifiers = {[object Object]},\n keywords = {Algorithms,Chromosome Mapping,Chromosome Mapping: methods,DNA,DNA Mutational Analysis,DNA Mutational Analysis: methods,DNA Transposable Elements,DNA Transposable Elements: genetics,DNA: methods,Evolution,Linkage Disequilibrium,Linkage Disequilibrium: genetics,Molecular,Sequence Alignment,Sequence Alignment: methods,Sequence Analysis},\n pages = {380-394},\n volume = {3},\n websites = {http://www.ncbi.nlm.nih.gov/pubmed/17085847,http://www.computer.org/portal/web/csdl/doi/10.1109/tcbb.2006.56},\n month = {10},\n publisher = {Published by the IEEE CS, CI, and EMB Societies & the ACM},\n city = {Los Alamitos, CA, USA},\n id = {87436cd8-5b57-349e-bd20-d831b9b9a415},\n created = {2009-09-25T17:31:36.000Z},\n accessed = {2011-06-07},\n file_attached = {true},\n profile_id = {192e9f37-d4de-3f1f-95dc-8b4ae5980aa4},\n last_modified = {2013-04-22T09:24:01.000Z},\n tags = {genome rearrangements,sorting by transpositions},\n read = {true},\n starred = {false},\n authored = {true},\n confirmed = {true},\n hidden = {false},\n citation_key = {Labarre2006},\n source_type = {article},\n abstract = {The problem of sorting by transpositions asks for a sequence of adjacent interval exchanges that sorts a permutation and is of the shortest possible length. The distance of the permutation is defined as the length of such a sequence. Despite the apparently intuitive nature of this problem, introduced in 1995 by Bafna and Pevzner, the complexity of both finding an optimal sequence and computing the distance remains open today. In this paper, we establish connections between two different graph representations of permutations, which allows us to compute the distance of a few non-trivial classes of permutations in linear time and space, bypassing the use of any graph structure. By showing that every permutation can be obtained from one of these classes, we prove a new tight upper bound on the transposition distance. Finally, we give improved bounds on some other families of permutations and prove formulas for computing the exact distance of other classes of permutations, again in polynomial time.},\n bibtype = {article},\n author = {Labarre, Anthony},\n journal = {IEEE/ACM Transactions on Computational Biology and Bioinformatics},\n number = {4}\n}","author_short":["Labarre, A."],"urls":{"Paper":"http://bibbase.org/service/mendeley/192e9f37-d4de-3f1f-95dc-8b4ae5980aa4/file/3a8845d4-17a4-478c-2a53-d9ceb2c96237/2006-New_bounds_and_tractable_instances_for_the_transposition_distance.pdf.pdf","Website":"http://www.ncbi.nlm.nih.gov/pubmed/17085847,http://www.computer.org/portal/web/csdl/doi/10.1109/tcbb.2006.56"},"bibbaseid":"labarre-newboundsandtractableinstancesforthetranspositiondistance-2006","role":"author","keyword":["Algorithms","Chromosome Mapping","Chromosome Mapping: methods","DNA","DNA Mutational Analysis","DNA Mutational Analysis: methods","DNA Transposable Elements","DNA Transposable Elements: genetics","DNA: methods","Evolution","Linkage Disequilibrium","Linkage Disequilibrium: genetics","Molecular","Sequence Alignment","Sequence Alignment: methods","Sequence Analysis"],"downloads":0},"search_terms":["new","bounds","tractable","instances","transposition","distance","labarre"],"keywords":["algorithms","chromosome mapping","chromosome mapping: methods","dna","dna mutational analysis","dna mutational analysis: methods","dna transposable elements","dna transposable elements: genetics","dna: methods","evolution","linkage disequilibrium","linkage disequilibrium: genetics","molecular","sequence alignment","sequence alignment: methods","sequence analysis"],"authorIDs":[]}