Display Settings:


Send to:

Choose Destination

LSHPlace: fast phylogenetic placement using locality-sensitive hashing.

Author information

  • 1David R. Cheriton School of Computer Science, University of Waterloo, Waterloo ON N2L 3G1, Canada. browndg@uwaterloo.ca


We consider the problem of phylogenetic placement, in which large numbers of sequences (often next-generation sequencing reads) are placed onto an existing phylogenetic tree. We adapt our recent work on phylogenetic tree inference, which uses ancestral sequence reconstruction and locality-sensitive hashing, to this domain. With these ideas, new sequences can be placed onto trees with high fidelity in strikingly fast runtimes. Our results are two orders of magnitude faster than existing programs for this domain, and show a modest accuracy tradeoff. Our results offer the possibility of analyzing many more reads in a next-generation sequencing project than is currently possible.

[PubMed - indexed for MEDLINE]
Free full text
PubMed Commons home

PubMed Commons

How to join PubMed Commons

    Supplemental Content

    Full text links

    Icon for World Scientific Publishing Company
    Loading ...
    Write to the Help Desk