LSHPlace: Fast Phylogenetic Placement Using Locality-Sensitive Hashing


Daniel G. Brown1, Jakub Truszkowski2



David R. Cheriton School of Computer Science University of Waterloo
Email: browndg@uwaterloo.ca

Pacific Symposium on Biocomputing 18:310-319(2013)


Abstract

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 ?delity in strikingly fast runtimes. Our results are two orders of magnitude faster than existing programs for this domain, and show a modest accuracy tradeo?. Our results o?er the possibility of analyzing many more reads in a next-generation sequencing project than is currently possible.


[Full-Text PDF] [PSB Home Page]