• Admin
    UC Research Repository
    View Item 
       
    • UC Home
    • Library
    • UC Research Repository
    • College of Engineering
    • Engineering: Reports
    • View Item
       
    • UC Home
    • Library
    • UC Research Repository
    • College of Engineering
    • Engineering: Reports
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Browse

    All of the RepositoryCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    Statistics

    View Usage Statistics

    Quantifying hybridization in realistic time

    Thumbnail
    View/Open
    collins_linz_semple_ucdms2009-3_report.pdf (998.0Kb)
    Author
    Collins, J. S.
    Linz, S.
    Semple, C.
    Date
    2009
    Permanent Link
    http://hdl.handle.net/10092/11473

    Recently, numerous practical and theoretical studies in evolutionary biology aim at calculating the extent to which reticulation-for example horizontal gene transfer, hybridization, or recombination-has influenced the evolution for a set of present-day species. It has been shown that inferring the minimum number of hybridization events that is needed to simultaneously explain the evolutionary history for a set of trees is an NP-hard and also fixed-parameter tractable problem. In this paper, we give a new fixed-parameter algorithm for computing the minimum number of hybridization events for when two rooted binary phylogenetic trees are given. This newly developed algorithm is based on interleaving-a technique using repeated kernelization steps that are applied throughout the exhaustive search part of a fixed-parameter algorithm. To show that our algorithm runs efficiently to be applicable to a wide range of practical problem instances, we apply it to a grass data set and highlight the significant improvements in terms of running times in comparison to an algorithm which has previously been implemented.

    Subjects
    reticulate evolution
     
    hybridization
     
    agreement forests
     
    interleaving
     
    fixed-parameter tractability
     
    Field of Research::01 - Mathematical Sciences::0102 - Applied Mathematics::010202 - Biological Mathematics
     
    Field of Research::06 - Biological Sciences::0604 - Genetics::060409 - Molecular Evolution
    Collections
    • Engineering: Reports [695]
    Rights
    https://canterbury.libguides.com/rights/theses

    UC Research Repository
    University Library
    University of Canterbury
    Private Bag 4800
    Christchurch 8140

    Phone
    364 2987 ext 8718

    Email
    ucresearchrepository@canterbury.ac.nz

    Follow us
    FacebookTwitterYoutube

    © University of Canterbury Library
    Send Feedback | Contact Us