Show simple item record

dc.contributor.authorGuyer, Scott Aen_US
dc.contributor.authorHeath, Lenwood S.en_US
dc.contributor.authorVergara, John Paul C.en_US
dc.date.accessioned2013-06-19T14:35:54Z
dc.date.available2013-06-19T14:35:54Z
dc.date.issued1997-11-01
dc.identifierhttp://eprints.cs.vt.edu/archive/00000477/en_US
dc.identifier.urihttp://hdl.handle.net/10919/19970
dc.description.abstractSorting 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.en_US
dc.format.mimetypeapplication/postscripten_US
dc.publisherDepartment of Computer Science, Virginia Polytechnic Institute & State Universityen_US
dc.relation.ispartofHistorical Collection(Till Dec 2001)en_US
dc.titleSubsequence and Run Heuristics for Sorting by Transpositionsen_US
dc.typeTechnical reporten_US
dc.identifier.trnumberTR-97-20en_US
dc.type.dcmitypeTexten_US
dc.identifier.sourceurlhttp://eprints.cs.vt.edu/archive/00000477/01/TR-97-20.ps


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record