• Login
    View Item 
    •   MINDS@UW Home
    • MINDS@UW Whitewater
    • Master's Theses--UW-Whitewater
    • View Item
    •   MINDS@UW Home
    • MINDS@UW Whitewater
    • Master's Theses--UW-Whitewater
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    A simple, space-efficient algorithm for detecting start and stop codons in DNA

    Thumbnail
    File(s)
    ScottSchoellerThesisV4.pdf (244.4Kb)
    Date
    2021-04
    Author
    Schoeller, Scott J.
    Publisher
    University of Wisconsin - Whitewater
    Advisor(s)
    Oster, Zachary
    Ganguly, Arnab
    Veldkamp, Christopher
    Metadata
    Show full item record
    Abstract
    The brute force algorithm for string matching has a worst-case execution complexity of O(MN), where N is the length of the entire string and M is the length of the substring to be matched. The efficiency of brute-force matching is insufficient for biological applications due to the sheer size of bioinformatics datasets. This thesis describes an algorithm that uses bit compression techniques to represent multiple codons in a single Python integer. It was proven that with exact matching steps, the search algorithm is as accurate as brute-force matching with significantly higher efficiency, as this algorithm runs in O(N) time and space, with minimal memory overhead. While the bit-based algorithm is not more space-efficient in a theoretical sense, it is more efficient practically as we have observed significant memory savings compared to the size of the original string.
    Subject
    Bioinformatics
    DNA
    Permanent Link
    http://digital.library.wisc.edu/1793/82249
    Description
    This file was last viewed in Adobe Acrobat Pro.
    Part of
    • Master's Theses--UW-Whitewater

    Contact Us | Send Feedback
     

     

    Browse

    All of MINDS@UWCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    LoginRegister

    Contact Us | Send Feedback