This Article Full Text Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Citation Map Services Email this article to a friend Similar articles in this journal Similar articles in PubMed Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Kalafus, K. J. Articles by Milosavljevic, A. Search for Related Content PubMed PubMed Citation Articles by Kalafus, K. J. Articles by Milosavljevic, A. Social Bookmarking                   What's this?

Methods

Pash: Efficient Genome-Scale Sequence Anchoring by Positional Hashing

¹ Program in Structural and Computational Biology and Molecular Biophysics, Department of Molecular and Human Genetics, Baylor College of Medicine, Houston, Texas, 77030, USA ² Bioinformatics Research Laboratory, Department of Molecular and Human Genetics, Baylor College of Medicine, Houston, Texas, 77030, USA ³ Human Genome Sequencing Center, Department of Molecular and Human Genetics, Baylor College of Medicine, Houston, Texas, 77030, USA

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.

⁴ Corresponding author.
E-MAIL amilosav{at}bcm.tmc.edu; FAX (713) 798-4373.

CiteULike    Connotea    Del.icio.us    Digg    Reddit    Technorati    What's this?

This article has been cited by other articles:

				C. M. Bergman and H. Quesneville Discovering and detecting transposable elements in genome sequences Brief Bioinform, November 1, 2007; 8(6): 382 - 392. [Abstract] [Full Text] [PDF]

				Rhesus Macaque Genome Sequencing and Analysis Cons, R. A. Gibbs, J. Rogers, M. G. Katze, R. Bumgarner, G. M. Weinstock, E. R. Mardis, K. A. Remington, R. L. Strausberg, J. C. Venter, et al. Evolutionary and Biomedical Insights from the Rhesus Macaque Genome Science, April 13, 2007; 316(5822): 222 - 234. [Abstract] [Full Text] [PDF]

				R. A. Harris, J. Rogers, and A. Milosavljevic Human-Specific Changes of Genome Structure Detected by Genomic Triangulation Science, April 13, 2007; 316(5822): 235 - 237. [Abstract] [Full Text] [PDF]

				T. D. Wu and C. K. Watanabe GMAP: a genomic mapping and alignment program for mRNA and EST sequences Bioinformatics, May 1, 2005; 21(9): 1859 - 1875. [Abstract] [Full Text] [PDF]

				S. Zhao, J. Shetty, L. Hou, A. Delcher, B. Zhu, K. Osoegawa, P. de Jong, W. C. Nierman, R. L. Strausberg, and C. M. Fraser Human, Mouse, and Rat Genome Large-Scale Rearrangements: Stability Versus Speciation Genome Res., October 1, 2004; 14(10a): 1851 - 1860. [Abstract] [Full Text] [PDF]