Skip Navigation

This Article
Right arrow FREE Full Text (Print PDF) Freely available
Right arrow FREE Full Text (Screen PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Similar articles in PubMed
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrow Search for citing articles in:
ISI Web of Science (147)
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Ma, B.
Right arrow Articles by Li, M.
Right arrow Search for Related Content
PubMed
Right arrow PubMed Citation
Right arrow Articles by Ma, B.
Right arrow Articles by Li, M.
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

Bioinformatics Vol. 18 no. 3 2002
Pages 440-445
© 2002 Oxford University Press

PatternHunter: faster and more sensitive homology search

Bin Ma 1, John Tromp 2 and Ming Li 3

1 Computer Science Department, University of Western Ontario, London N6A 5B8, Canada
2 Bioinformatics Solutions Inc., 145 Columbia Street West, Waterloo, Ont. N2L 3L2, Canada
3 Computer Science Department, University of Waterloo, Waterloo, Ont. N2L 3G1, Canadaand Bioinformatics Lab, Computer Science Department, University of California, Santa Barbara, CA 93106, USA

Received on August 24, 2001 ; revised on October 10, 2001 ; accepted on October 15, 2001

Motivation: Genomics and proteomics studies routinely depend on homology searches based on the strategy of finding short seed matches which are then extended. The exploding genomic data growth presents a dilemma for DNA homology search techniques: increasing seed size decreases sensitivity whereas decreasing seed size slows down computation.

Results: We present a new homology search algorithm ‘PatternHunter’ that uses a novel seed model for increased sensitivity and new hit-processing techniques for significantly increased speed. At Blast levels of sensitivity, PatternHunter is able to find homologies between sequences as large as human chromosomes, in mere hours on a desktop.

Availability: PatternHunter is available at http://www.bioinformaticssolutions.com, as a commercial package. It runs on all platforms that support Java. PatternHunter technology is being patented; commercial use requires a license from BSI, while non-commercial use will be free.

Contact: mli{at}cs.ucsb.edu


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?


This article has been cited by other articles:


Home page
 Nucleic Acids ResHome page
O. Gotoh
A space-efficient and accurate method for mapping and aligning cDNA sequences onto genomic sequence
Nucleic Acids Res., May 1, 2008; 36(8): 2630 - 2638.
[Abstract] [Full Text] [PDF]

Home page
 Nucleic Acids ResHome page
D. L. Wheeler, T. Barrett, D. A. Benson, S. H. Bryant, K. Canese, V. Chetvernin, D. M. Church, M. DiCuccio, R. Edgar, S. Federhen, et al.
Database resources of the National Center for Biotechnology Information
Nucleic Acids Res., January 11, 2008; 36(suppl_1): D13 - D21.
[Abstract] [Full Text] [PDF]

Home page
 BioinformaticsHome page
L. Ilie and S. Ilie
Multiple spaced seeds for homology search
Bioinformatics, November 15, 2007; 23(22): 2969 - 2977.
[Abstract] [Full Text] [PDF]

Home page
 Mol Biol EvolHome page
D. E. Neafsey and J. E. Galagan
Dual Modes of Natural Selection on Upstream Open Reading Frames
Mol. Biol. Evol., August 1, 2007; 24(8): 1744 - 1751.
[Abstract] [Full Text] [PDF]

Home page
 BioinformaticsHome page
X. Cui, T. Vinar, B. Brejova, D. Shasha, and M. Li
Homology search for genes
Bioinformatics, July 1, 2007; 23(13): i97 - i103.
[Abstract] [Full Text] [PDF]

Home page
 BioinformaticsHome page
S. Feng and E. R.M. Tillier
A fast and flexible approach to oligonucleotide probe design for genomes and gene families
Bioinformatics, May 15, 2007; 23(10): 1195 - 1202.
[Abstract] [Full Text] [PDF]

Home page
 Mol Biol EvolHome page
S. W. Roy, D. Penny, and D. E. Neafsey
Evolutionary Conservation of UTR Intron Boundaries in Cryptococcus
Mol. Biol. Evol., May 1, 2007; 24(5): 1140 - 1148.
[Abstract] [Full Text] [PDF]

Home page
 BioinformaticsHome page
J. Zhang, B. Jiang, M. Li, J. Tromp, X. Zhang, and M. Q. Zhang
Computing exact P-values for DNA motifs
Bioinformatics, March 1, 2007; 23(5): 531 - 537.
[Abstract] [Full Text] [PDF]

Home page
 Nucleic Acids ResHome page
X. Huang and D. L. Brutlag
Dynamic use of multiple parameter sets in sequence alignment
Nucleic Acids Res., January 28, 2007; 35(2): 678 - 686.
[Abstract] [Full Text] [PDF]

Home page
 Nucleic Acids ResHome page
D. L. Wheeler, T. Barrett, D. A. Benson, S. H. Bryant, K. Canese, V. Chetvernin, D. M. Church, M. DiCuccio, R. Edgar, S. Federhen, et al.
Database resources of the National Center for Biotechnology Information
Nucleic Acids Res., January 12, 2007; 35(suppl_1): D5 - D12.
[Abstract] [Full Text] [PDF]

Home page
 Genome ResHome page
C. Soderlund, W. Nelson, A. Shoemaker, and A. Paterson
SyMAP: A system for discovering and viewing syntenic regions of FPC maps.
Genome Res., September 1, 2006; 16(9): 1159 - 1168.
[Abstract] [Full Text] [PDF]

Home page
 Genome ResHome page
J. Flannick, A. Novak, B. S. Srinivasan, H. H. McAdams, and S. Batzoglou
Graemlin: General and robust alignment of multiple large interaction networks
Genome Res., September 1, 2006; 16(9): 1169 - 1181.
[Abstract] [Full Text] [PDF]

Home page
 BioinformaticsHome page
R. Engels, T. Yu, C. Burge, J. P. Mesirov, D. DeCaprio, and J. E. Galagan
Combo: a whole genome comparative browser
Bioinformatics, July 15, 2006; 22(14): 1782 - 1783.
[Abstract] [Full Text] [PDF]

Home page
 BioinformaticsHome page
J. Kohler, J. Baumbach, J. Taubert, M. Specht, A. Skusa, A. Ruegg, C. Rawlings, P. Verrier, and S. Philippi
Graph-based analysis and visualization of experimental results with ONDEX
Bioinformatics, June 1, 2006; 22(11): 1383 - 1390.
[Abstract] [Full Text] [PDF]

Home page
 Hum Mol GenetHome page
C. N. Dewey and L. Pachter
Evolution at the nucleotide level: the problem of multiple whole-genome alignment.
Hum. Mol. Genet., April 15, 2006; 15(suppl_1): R51 - R56.
[Abstract] [Full Text] [PDF]

Home page
 Journal of Information ScienceHome page
J.-I. Won, S. Park, J.-H. Yoon, and S.-W. Kim
An efficient approach for sequence matching in large DNA databases
Journal of Information Science, February 1, 2006; 32(1): 88 - 104.
[Abstract] [PDF]

Home page
 BioinformaticsHome page
A. Morgulis, E. M. Gertz, A. A. Schaffer, and R. Agarwala
WindowMasker: window-based masker for sequenced genomes
Bioinformatics, January 15, 2006; 22(2): 134 - 141.
[Abstract] [Full Text] [PDF]

Home page
 Nucleic Acids ResHome page
X. Huang, S.-P. Yang, A. T. Chinwalla, L. W. Hillier, P. Minx, E. R. Mardis, and R. K. Wilson
Application of a superword array in genome assembly
Nucleic Acids Res., January 5, 2006; 34(1): 201 - 205.
[Abstract] [Full Text] [PDF]

Home page
 BioinformaticsHome page
W. Huang, D. M. Umbach, and L. Li
Accurate anchoring alignment of divergent sequences
Bioinformatics, January 1, 2006; 22(1): 29 - 34.
[Abstract] [Full Text] [PDF]

Home page
 Nucleic Acids ResHome page
D. L. Wheeler, T. Barrett, D. A. Benson, S. H. Bryant, K. Canese, V. Chetvernin, D. M. Church, M. DiCuccio, R. Edgar, S. Federhen, et al.
Database resources of the National Center for Biotechnology Information
Nucleic Acids Res., January 1, 2006; 34(suppl_1): D173 - D180.
[Abstract] [Full Text] [PDF]

Home page
 Proc. Natl. Acad. Sci. USAHome page
H.-R. Lee, W. Zhang, T. Langdon, W. Jin, H. Yan, Z. Cheng, and J. Jiang
From The Cover: Chromatin immunoprecipitation cloning reveals rapid evolutionary patterns of centromeric DNA in Oryza species
PNAS, August 16, 2005; 102(33): 11793 - 11798.
[Abstract] [Full Text] [PDF]

Home page
 Nucleic Acids ResHome page
J. Flannick and S. Batzoglou
Using multiple alignments to improve seeded local alignment algorithms
Nucleic Acids Res., August 12, 2005; 33(14): 4563 - 4577.
[Abstract] [Full Text] [PDF]

Home page
 Nucleic Acids ResHome page
L. Noe and G. Kucherov
YASS: enhancing the sensitivity of DNA similarity search
Nucleic Acids Res., July 1, 2005; 33(suppl_2): W540 - W543.
[Abstract] [Full Text] [PDF]

Home page
 Int. J. Syst. Evol. Microbiol.Home page
R. Rivas, C. Gutierrez, A. Abril, P. F. Mateos, E. Martinez-Molina, A. Ventosa, and E. Velazquez
Paenibacillus rhizosphaerae sp. nov., isolated from the rhizosphere of Cicer arietinum
Int J Syst Evol Microbiol, May 1, 2005; 55(3): 1305 - 1309.
[Abstract] [Full Text] [PDF]

Home page
 BioinformaticsHome page
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]

Home page
 BioinformaticsHome page
M. Itoh, S. Goto, T. Akutsu, and M. Kanehisa
Fast and accurate database homology search using upper bounds of local alignment scores
Bioinformatics, April 1, 2005; 21(7): 912 - 921.
[Abstract] [Full Text] [PDF]

Home page
 BioinformaticsHome page
D. Kisman, M. Li, B. Ma, and L. Wang
tPatternHunter: gapped, fast and sensitive translated homology search
Bioinformatics, February 15, 2005; 21(4): 542 - 544.
[Abstract] [Full Text] [PDF]

Home page
 Genome ResHome page
L. Florea, V. Di Francesco, J. Miller, R. Turner, A. Yao, M. Harris, B. Walenz, C. Mobarry, G. V. Merkulov, R. Charlab, et al.
Gene and alternative splicing annotation with AIR
Genome Res., January 1, 2005; 15(1): 54 - 66.
[Abstract] [Full Text] [PDF]

Home page
 Nucleic Acids ResHome page
D. L. Wheeler, T. Barrett, D. A. Benson, S. H. Bryant, K. Canese, D. M. Church, M. DiCuccio, R. Edgar, S. Federhen, W. Helmberg, et al.
Database resources of the National Center for Biotechnology Information
Nucleic Acids Res., January 1, 2005; 33(suppl_1): D39 - D45.
[Abstract] [Full Text] [PDF]

Home page
 Genome ResHome page
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]

Home page
 Nucleic Acids ResHome page
S. McGinnis and T. L. Madden
BLAST: at the core of a powerful and diverse set of sequence analysis tools
Nucleic Acids Res., July 1, 2004; 32(suppl_2): W20 - W25.
[Abstract] [Full Text] [PDF]

Home page
 Nucleic Acids ResHome page
K. Rotmistrovsky, W. Jang, and G. D. Schuler
A web server for performing electronic PCR
Nucleic Acids Res., July 1, 2004; 32(suppl_2): W108 - W112.
[Abstract] [Full Text] [PDF]

Home page
 J. Biol. Chem.Home page
T. A. Stevens, J. S. Iacovoni, D. B. Edelman, and R. Meech
Identification of Novel Binding Elements and Gene Targets for the Homeodomain Protein BARX2
J. Biol. Chem., April 9, 2004; 279(15): 14520 - 14530.
[Abstract] [Full Text] [PDF]

Home page
 Genome ResHome page
G. Bourque, P. A. Pevzner, and G. Tesler
Reconstructing the Genomic Architecture of Ancestral Mammals: Lessons From Human, Mouse, and Rat Genomes
Genome Res., April 1, 2004; 14(4): 507 - 516.
[Abstract] [Full Text] [PDF]

Home page
 Genome ResHome page
K. J. Kalafus, A. R. Jackson, and A. Milosavljevic
Pash: Efficient Genome-Scale Sequence Anchoring by Positional Hashing
Genome Res., April 1, 2004; 14(4): 672 - 678.
[Abstract] [Full Text] [PDF]

Home page
 Genome ResHome page
M. Brudno, A. Poliakov, A. Salamov, G. M. Cooper, A. Sidow, E. M. Rubin, V. Solovyev, S. Batzoglou, and I. Dubchak
Automated Whole-Genome Multiple Alignment of Rat, Mouse, and Human
Genome Res., April 1, 2004; 14(4): 685 - 692.
[Abstract] [Full Text] [PDF]

Home page
 Operations ResearchHome page
A. E. Abbas and S. P. Holmes
Bioinformatics and Management Science: Some Common Tools and Techniques
Operations Research, March 1, 2004; 52(2): 165 - 190.
[Abstract] [PDF]

Home page
 Genome ResHome page
H. Riethman, A. Ambrosini, C. Castaneda, J. Finklestein, X.-L. Hu, U. Mudunuri, S. Paul, and J. Wei
Mapping and Initial Analysis of Human Subtelomeric Sequence Assemblies
Genome Res., January 1, 2004; 14(1): 18 - 28.
[Abstract] [Full Text] [PDF]

Home page
 Nucleic Acids ResHome page
D. L. Wheeler, D. M. Church, R. Edgar, S. Federhen, W. Helmberg, T. L. Madden, J. U. Pontius, G. D. Schuler, L. M. Schriml, E. Sequeira, et al.
Database resources of the National Center for Biotechnology Information: update
Nucleic Acids Res., January 1, 2004; 32(90001): D35 - 40.
[Abstract] [Full Text] [PDF]

Home page
 Nucleic Acids ResHome page
V. Gotea, V. Veeramachaneni, and W. Makalowski
Mastering seeds for genomic size nucleotide BLAST searches
Nucleic Acids Res., December 1, 2003; 31(23): 6935 - 6941.
[Abstract] [Full Text] [PDF]

Home page
 Nucleic Acids ResHome page
A. Nekrutenko, W.-Y. Chung, and W.-H. Li
ETOPE: evolutionary test of predicted exons
Nucleic Acids Res., July 1, 2003; 31(13): 3564 - 3567.
[Abstract] [Full Text] [PDF]

Home page
 ScienceHome page
S. W. Scherer, J. Cheung, J. R. MacDonald, L. R. Osborne, K. Nakabayashi, J.-A. Herbrick, A. R. Carson, L. Parker-Katiraee, J. Skaug, R. Khaja, et al.
Human Chromosome 7: DNA Sequence and Biology
Science, May 2, 2003; 300(5620): 767 - 772.
[Abstract] [Full Text] [PDF]

Home page
 Nucleic Acids ResHome page
D. L. Wheeler, D. M. Church, S. Federhen, A. E. Lash, T. L. Madden, J. U. Pontius, G. D. Schuler, L. M. Schriml, E. Sequeira, T. A. Tatusova, et al.
Database resources of the National Center for Biotechnology
Nucleic Acids Res., January 1, 2003; 31(1): 28 - 33.
[Abstract] [Full Text] [PDF]

Home page
 Genome ResHome page
O. Couronne, A. Poliakov, N. Bray, T. Ishkhanov, D. Ryaboy, E. Rubin, L. Pachter, and I. Dubchak
Strategies and Tools for Whole-Genome Alignments
Genome Res., January 1, 2003; 13(1): 73 - 80.
[Abstract] [Full Text] [PDF]

Home page
 Genome ResHome page
P. Pevzner and G. Tesler
Genome Rearrangements in Mammalian Evolution: Lessons From Human and Mouse Genomes
Genome Res., January 1, 2003; 13(1): 37 - 45.
[Abstract] [Full Text] [PDF]

Home page
 Genome ResHome page
S. Schwartz, W. J. Kent, A. Smit, Z. Zhang, R. Baertsch, R. C. Hardison, D. Haussler, and W. Miller
Human-Mouse Alignments with BLASTZ
Genome Res., January 1, 2003; 13(1): 103 - 107.
[Abstract] [Full Text] [PDF]


Disclaimer:
Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.