Shared more. Cited more. Safe forever.
    • advanced search
    • submit works
    • about
    • help
    • contact us
    • login
    View Item 
    •   MOspace Home
    • University of Missouri-Columbia
    • Graduate School - MU Theses and Dissertations (MU)
    • Theses and Dissertations (MU)
    • Theses (MU)
    • 2010 Theses (MU)
    • 2010 MU theses - Access restricted to UM
    • View Item
    •   MOspace Home
    • University of Missouri-Columbia
    • Graduate School - MU Theses and Dissertations (MU)
    • Theses and Dissertations (MU)
    • Theses (MU)
    • 2010 Theses (MU)
    • 2010 MU theses - Access restricted to UM
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.
    advanced searchsubmit worksabouthelpcontact us

    Browse

    All of MOspaceCommunities & CollectionsDate IssuedAuthor/ContributorTitleIdentifierThesis DepartmentThesis AdvisorThesis SemesterThis CollectionDate IssuedAuthor/ContributorTitleIdentifierThesis DepartmentThesis AdvisorThesis Semester

    Statistics

    Most Popular ItemsStatistics by CountryMost Popular AuthorsStatistics by Referrer

    A fast multiple longest common subsequence (MLCS) algorithm

    Wang, Qingguo
    View/Open
    [PDF] public.pdf (2.739Kb)
    [PDF] short.pdf (33.93Kb)
    [PDF] research.pdf (338.4Kb)
    Date
    2010
    Format
    Thesis
    Metadata
    [+] Show full item record
    Abstract
    [ACCESS RESTRICTED TO THE UNIVERSITY OF MISSOURI AT REQUEST OF AUTHOR.] 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.
    URI
    https://hdl.handle.net/10355/8135
    https://doi.org/10.32469/10355/8135
    Degree
    M.S.
    Thesis Department
    Computer science (MU)
    Rights
    Access is limited to the campuses of the University of Missouri.
    Collections
    • Computer Science electronic theses and dissertations (MU)
    • 2010 MU theses - Access restricted to UM

    Send Feedback
    hosted by University of Missouri Library Systems
     

     


    Send Feedback
    hosted by University of Missouri Library Systems