Subsequence and Run Heuristics for Sorting by Transpositions

Simple item page
dc.contributor.authorGuyer, Scott A.en
dc.contributor.authorHeath, Lenwood S.en
dc.contributor.authorVergara, John Paul C.en
dc.contributor.departmentComputer Scienceen
dc.date.accessioned2013-06-19T14:35:54Zen
dc.date.available2013-06-19T14:35:54Zen
dc.date.issued1997-11-01en
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
dc.format.mimetypeapplication/postscripten
dc.identifierhttp://eprints.cs.vt.edu/archive/00000477/en
dc.identifier.sourceurlhttp://eprints.cs.vt.edu/archive/00000477/01/TR-97-20.psen
dc.identifier.trnumberTR-97-20en
dc.identifier.urihttp://hdl.handle.net/10919/19970en
dc.language.isoenen
dc.publisherDepartment of Computer Science, Virginia Polytechnic Institute & State Universityen
dc.relation.ispartofHistorical Collection(Till Dec 2001)en
dc.rightsIn Copyrighten
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.titleSubsequence and Run Heuristics for Sorting by Transpositionsen
dc.typeTechnical reporten
dc.type.dcmitypeTexten

Files

Original bundle
Now showing 1 - 1 of 1
Name:
TR-97-20.ps
Size:
99.93 KB
Format:
Postscript Files
Download

Collections

Computer Science Technical Reports