Pash: efficient genome-scale sequence anchoring by Positional Hashing.

TitlePash: efficient genome-scale sequence anchoring by Positional Hashing.
Publication TypeJournal Article
Year of Publication2004
AuthorsKalafus, KJ, Jackson, AR, Milosavljevic, A
JournalGenome Res
Volume14
Issue4
Pagination672-8
Date Published2004 Apr
ISSN1088-9051
KeywordsAnimals, Chromosome Mapping, Cluster Analysis, Computational Biology, DNA, Genome, Genome, Human, Humans, Mice, Pan troglodytes, Rats, Sensitivity and Specificity, Software
Abstract

Pash is a computer program for efficient, parallel, all-against-all comparison of very long DNA sequences. Pash implements Positional Hashing, a novel parallelizable method for sequence comparison based on k-mer representation of sequences. The Positional Hashing method breaks the comparison problem in a unique way that avoids the quadratic penalty encountered with other sensitive methods and confers inherent low-level parallelism. Furthermore, Positional Hashing allows one to readily and predictably trade between sensitivity and speed. In a simulated comparison task, anchoring computationally mutated reads onto a genome, the sensitivity of Pash was equal to or greater than that of BLAST and BLAT, with Pash outperforming these programs as the reads became shorter and less similar to the genome. Using modest computing resources, we employed Pash for two large-scale sequence comparison tasks: comparison of three mammalian genomes, and anchoring millions of chimpanzee whole-genome shotgun sequencing reads onto the human genome. The results of these comparisons by Pash agree with those computed by other methods that use more than an order of magnitude more computing resources. These results confirm the sensitivity of Positional Hashing.

DOI10.1101/gr.1963804
Alternate JournalGenome Res.
PubMed ID15060009
PubMed Central IDPMC383312