Sorting signed permutations by inversions in O(nlogn) time
The study of genomic inversions (or reversals) has been a mainstay of computational genomics for nearly 20 years. After the initial breakthrough of Hannenhalli and Pevzner, who gave the first polynomial-time algorithm for sorting signed permutations by inversions, improved algorithms have been designed, culminating with an optimal linear-time algorithm for computing the inversion distance and a subquadratic algorithm for providing a shortest sequence of inversions-also known as sorting by inversions. Remaining open was the question of whether sorting by inversions Could be done in O(n log n) time.
WOS:000266195700028
2009
Berlin
Lecture Notes in Computer Science; 5541
386
399
REVIEWED
Event name | Event place | Event date |
Tucson, AZ, USA | May 18-21, 2009 | |