Browsing by Author "Guyer, Scott A."
Now showing 1 - 1 of 1
Results Per Page
Sort Options
- Subsequence and Run Heuristics for Sorting by TranspositionsGuyer, Scott A.; Heath, Lenwood S.; Vergara, John Paul C. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1997-11-01)Sorting by tranpositions is the problem of finding the minimum number of transpositions required to sort a permutation pi. A transposition involves repositioning a contiguous sequence (block) of elements by inserting it elsewhere in the permutation. The problem has applications in the study of genome rearrangements and phylogeny reconstruction. In this paper, several heuristics based on analyses of subsequences and runs in a permutation are employed. Experimental results are provided. The algorithm based on the longest increasing subsequence in a permutation appears most promising.