• Login
    View Item 
    •   Carroll Scholars Home
    • Mathematics, Engineering and Computer Science
    • Mathematics, Engineering and Computer Science Undergraduate Theses
    • View Item
    •   Carroll Scholars Home
    • Mathematics, Engineering and Computer Science
    • Mathematics, Engineering and Computer Science Undergraduate Theses
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    The Minimum Letter Flip Problem for Haplotyping a Single Individual

    Thumbnail
    View/Open
    2006_LouieJ_THS_000711.pdf (2.351Mb)
    Author
    Louie, John
    Date of Issue
    2006-04-01
    Metadata
    Show full item record
    URI
    https://scholars.carroll.edu/handle/20.500.12647/3445
    Title
    The Minimum Letter Flip Problem for Haplotyping a Single Individual
    Type
    thesis
    Abstract
    When haplotyping a single individual, DNA is replicated, broken into smaller fragments, and then sequenced by a machine. The minimum letter flip problem is one approach to correcting errors that arise in shotgun sequencing. We refer to the minimum letter flip problem as stated in other texts as CGMLF. CGMLF changes a minimal number of single nucleotide polymorphisms (SNPs) to create a feasible SNP matrix. Since finding partitions that have this property is especially difficult, we relate CGMLF to several 2-median problem formulations. Our major result is that the CGMLF is equivalent to a non-polynomial 2-median problem formulation. We develop algorithms used to solve the 2-median problems and discuss their complexity. In conclusion, we develop inequality relations for our problem formulations based on minimum number of flips and prove that CGMLF can be bounded from above in polynomial time.
    Degree Awarded
    Bachelor's
    Semester
    Spring
    Department
    Mathematics, Engineering & Computer Science
    Collections
    • Mathematics, Engineering and Computer Science Undergraduate Theses

    Browse

    All of Carroll ScholarsCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    LoginRegister

    DSpace software copyright © 2002-2023  DuraSpace
    DSpace Express is a service operated by 
    Atmire NV