• Admin
    UC Research Repository
    View Item 
       
    • UC Home
    • Library
    • UC Research Repository
    • College of Engineering
    • Engineering: Journal Articles
    • View Item
       
    • UC Home
    • Library
    • UC Research Repository
    • College of Engineering
    • Engineering: Journal Articles
    • 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

    Tree reconstruction from multi-state characters

    Thumbnail
    View/Open
    45500_Main.pdf (159.4Kb)
    Author
    Semple, C.
    Steel, M.
    Date
    2002
    Permanent Link
    http://hdl.handle.net/10092/228

    In evolutionary biology, a character is a function from a set X of present-day species into a finite set of states. Suppose the species in X have evolved according to a bifurcating tree T. Biologists would like to use characters to infer this tree. Assume that is the result of an evolutionary process on T that has not involved reverse or parallel transitions, such characters are called homoplasy-free. In this case, provides direct combinatorial information about the underlying evolutionary tree T for X. We consider the question of how many homoplasy-free characters are required so that T can be correctly reconstructed. We first establish lower bounds showing that, when the number of states is bounded, the number of homoplasy-free characters required to reconstruct T grows (at least) linearly with the size of X. In contrast, our main result shows that, when the state space is sufficiently large, every bifurcating tree can be uniquely determined by just five homoplasy-free characters. We briefly describe the relevance of this result for some new types of genomic data, and for the amalgamation of evolutionary trees.

    Subjects
    tree
     
    character compatibility
     
    phylogeny
     
    chordal graph
     
    Fields of Research::230000 Mathematical Sciences::239900 Other Mathematical Sciences::239901 Biological Mathematics
    Collections
    • Engineering: Journal Articles [932]
    Rights
    http://library.canterbury.ac.nz/ir/rights.shtml

    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