[-] Show simple item record

dc.contributor.advisorShang, Yi, 1967-eng
dc.contributor.authorWang, Qingguoeng
dc.date.issued2010eng
dc.date.submitted2010 Springeng
dc.descriptionTitle from PDF of title page (University of Missouri--Columbia, viewed on June 30, 2010).eng
dc.descriptionThe entire thesis text is included in the research.pdf file; the official abstract appears in the short.pdf file; a non-technical public abstract appears in the public.pdf file.eng
dc.descriptionThesis advisor: Dr. Yi Shang.eng
dc.descriptionIncludes bibliographical references.eng
dc.descriptionM.S. University of Missouri--Columbia 2010.eng
dc.descriptionDissertations, Academic -- University of Missouri--Columbia -- Computer science.eng
dc.description.abstract[ACCESS RESTRICTED TO THE UNIVERSITY OF MISSOURI AT AUTHOR'S REQUEST.] Finding the longest common subsequence (LCS) of multiple strings is an NP-hard problem, with many applications in the areas of bioinformatics and computational genomics. Although significant efforts have been made to address the problem and its special cases, the increasing complexity and size of biological data require more efficient methods applicable to an arbitrary number of strings. In this thesis, we present a new algorithm for the general case of multiple LCS (or MLCS) problem, i.e., finding a LCS of any number of strings, and its parallel realization. The algorithm is based on the dominant point approach and employs a fast divide and- conquer technique to compute the dominant points. When applied to a case of 3 strings, our algorithm demonstrates the same performance as the fastest existing MLCS algorithm designed for that specific case. When applied to more than 3 strings, our algorithm is significantly faster than the best existing sequential methods, reaching up to 2-3 orders of magnitude faster speed on large-size problems. Finally, we present an efficient parallel implementation of the algorithm. Evaluating the parallel algorithm on a benchmark set of both random and biological sequences reveals a near-linear speed-up with respect to the sequential algorithm.eng
dc.format.extentx, 56 pageseng
dc.identifier.merlinb79557272eng
dc.identifier.oclc650110168eng
dc.identifier.urihttps://hdl.handle.net/10355/8135
dc.identifier.urihttps://doi.org/10.32469/10355/8135eng
dc.languageEnglisheng
dc.publisherUniversity of Missouri--Columbiaeng
dc.relation.ispartof2010 UM restricted theses (MU)eng
dc.relation.ispartofcommunityUniversity of Missouri-Columbia. Graduate School. Theses and Dissertations. Theses. 2010 Theseseng
dc.rightsAccess is limited to the campuses of the University of Missouri.eng
dc.subject.lcshParallel algorithmseng
dc.subject.lcshSequential analysiseng
dc.subject.lcshSequences (Mathematics)eng
dc.titleA fast multiple longest common subsequence (MLCS) algorithmeng
dc.typeThesiseng
thesis.degree.disciplineComputer science (MU)eng
thesis.degree.grantorUniversity of Missouri--Columbiaeng
thesis.degree.levelMasterseng
thesis.degree.nameM.S.eng


Files in this item

[PDF]
[PDF]
[PDF]

This item appears in the following Collection(s)

[-] Show simple item record