rdf-syntax-grammar
mods:
  schema location: http://www.loc.gov/mods/v3 http://www.loc.gov/standards/mods/v3/mods-3-2.xsd
  title info:
    title: Fast hash-based algorithms for analyzing large collections of evolutionary trees
  name:
    name part: Sul, Seung Jin.
    role:
      role term: creator
  name:
    name part: Williams, Tiffani L.
    role:
      role term: thesis advisor.
  type of resource: text
  genre: bibliography
  origin info:
    place:
      place term: txu
    date issued: 2011
    issuance: monographic
  language:
    language term: eng
  physical description:
    form: remote
    extent: 1 online resource.
  abstract: Phylogenetic analysis can produce easily tens of thousands of equally plausible evolutionary trees. Consensus trees and topological distance matrices are often used to summarize the evolutionary relationships among the trees of interest. However, current approaches are not designed to analyze very large tree collections. In this dissertation, we present two fast algorithms - HashCS and HashRF - for analyzing large collections of evolutionary trees based on a novel hash table data structure, which provides a convenient and fast approach to store and access the bipartition information collected from the tree collections. Our HashCS algorithm is a fast O(nt) technique for constructing consensus trees, where n is the number of taxa and t is the number of trees. By reprocessing the bipartition information in our hash table, HashCS constructs strict and majority consensus trees. In addition to a consensus algorithm, we design a fast topological distance algorithm called HashRF to compute the t x t Robinson-Foulds distance matrix, which requires O(nt) running time. A RF distance matrix provides plenty of data-mining opportunities to help researchers understand the evolutionary relationships contained in their collection of trees. We also introduce a series of extensions based on HashRF to provide researchers with more convenient set of tools for analyzing their trees. We provide extensive experimentation regarding the practical performance of our hash-based algorithms across a diverse collection of biological and artificial trees. Our results show that both algorithms easily outperform existing consensus and RF matrix implementations. For example, on our biological trees, HashCS and HashRF are 1.8 and 100 times faster than PAUP*, respectively. We show two real-world applications of our fast hashing algorithms: (i) comparing phylogenetic heuristic implementations, and (ii) clustering and visualizing trees. In our first application, we design novel methods to compare the Pau…
  note: by Seung Jin Sul.
  note: "Major Subject: Computer Science"
  note: Title from author supplied metadata (automated record created 2011-02-28 11:02:00).
  note: Electronic resource.
  note: Doctor of Philosophy Texas A&M University 2009 http://hdl.handle.net/1969.1/ETD-TAMU-2009-12-7591
  note: Includes bibliographical references.
  note: Text (Dissertation)
  subject:
    topic: Major computer science
  subject:
    topic: hash
  subject:
    topic: consensus tree
  subject:
    topic: phylogenetic analysis
  subject:
    topic: evolutionary tree
  subject:
    topic: Robinson-Foulds distance
  identifier: http://hdl.handle.net/1969.1/ETD-TAMU-2009-12-7591
  record info:
    record content source: TXA
    record creation date: 110309
    record change date: 20151202115718.0
    record identifier: in00002683165