The DOI matches its Crossref record; 12 of the 12 references it cites were found in a registry or an index.
PatternHunter: faster and more sensitive homology search
Abstract
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@cs.ucsb.edu
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Basic local alignment search tool
Altschul, S. F., Gish, W., Miller, W., Myers, E. W., & Lipman, D. J. (1990) · Journal of Molecular Biology · doi:10.1006/jmbi.1990.9999 · Cited by 98,669
Gapped BLAST and PSI-BLAST: a new generation of protein database search programs
Altschul, S. (1997) · Nucleic Acids Research · doi:10.1093/nar/25.17.3389 · Cited by 73,302
The sequence of the human genome
Venter, J. C., Adams, M. D., Myers, E. W., Li, P. W., Mural, R. J., Sutton, G. G., Smith, H. O., Yandell, M., Evans, C. A., Holt, R. A., et al. (2001) · Science · doi:10.1126/science.1058040 · Cited by 13,909
A Greedy Algorithm for Aligning DNA Sequences
Zhang, Z., Schwartz, S., Wagner, L., & Miller, W. (2000) · Journal of Computational Biology · doi:10.1089/10665270050081478 · Cited by 5,478
Approximate nearest neighbors: towards removing the curse of dimensionality
Indyk, P., & Motwani, R. (1998) · Proceedings of the thirtieth annual ACM symposium on Theory of computing - STOC '98 · doi:10.1145/276698.276876 · Cited by 4,188
Rapid and sensitive protein similarity searches
Lipman, D. J., & Pearson, W. R. (1985) · Science · doi:10.1126/science.2983426 · Cited by 4,033
BLAST 2 Sequences, a new tool for comparing protein and nucleotide sequences
Tatusova, T. A., & Madden, T. L. (1999) · FEMS Microbiology Letters · doi:10.1111/j.1574-6968.1999.tb13575.x · Cited by 1,789
A time-efficient, linear-space local similarity algorithm
Huang, X., & Miller, W. (1991) · Advances in Applied Mathematics · doi:10.1016/0196-8858(91)90017-d · Cited by 1,004
Delcher, A. L., Kasif, S., Fleischmann, R. D., Peterson, J., White, O., & Salzberg, S. L. (1999) · Nucleic Acids Research · doi:10.1093/nar/27.11.2369 · Cited by 893
Finding Motifs Using Random Projections
Buhler, J., & Tompa, M. (2002) · Journal of Computational Biology · doi:10.1089/10665270252935430 · Cited by 532
Cited by
Fast and accurate short read alignment with Burrows-Wheeler transform
Li, H., & Durbin, R. (2009) · Bioinformatics · doi:10.1093/bioinformatics/btp324 · Cited by 58,607
Ultrafast and memory-efficient alignment of short DNA sequences to the human genome.
Langmead, B., Trapnell, C., Pop, M., & Salzberg, S. L. (2009) · Genome Biology · doi:10.1186/gb-2009-10-3-r25 · Cited by 21,849
Fast and sensitive protein alignment using DIAMOND
Buchfink, B., Xie, C., & Huson, D. H. (2015) · Nature Methods · doi:10.1038/nmeth.3176 · Cited by 14,201
Fast and accurate long-read alignment with Burrows-Wheeler transform.
Li, H., & Durbin, R. (2010) · Bioinformatics · doi:10.1093/bioinformatics/btp698 · Cited by 12,063
Database resources of the National Center for Biotechnology Information: update
Wheeler, D. L. (2004) · Nucleic Acids Research · doi:10.1093/nar/gkh073 · Cited by 10,641
Initial sequencing and comparative analysis of the mouse genome
Mouse Genome Sequencing Consortium (2002) · Nature · doi:10.1038/nature01262 · Cited by 7,187
Sensitive protein alignments at tree-of-life scale using DIAMOND
Buchfink, B., Reuter, K., & Drost, H.-G. (2021) · Nature Methods · doi:10.1038/s41592-021-01101-x · Cited by 5,097
progressiveMauve: Multiple Genome Alignment with Gene Gain, Loss and Rearrangement
Darling, A. E., Mau, B., & Perna, N. T. (2010) · PLoS ONE · doi:10.1371/journal.pone.0011147 · Cited by 3,848
“A spaced seed pattern of length k and weight w [37] identifies the location of k-”
BackgroundMapping short DNA sequencing reads and calling variants using mapping quality scores
Li, H., Ruan, J., & Durbin, R. (2008) · Genome Research · doi:10.1101/gr.078212.108 · Cited by 2,638
Genome sequence, comparative analysis and haplotype structure of the domestic dog
members, B. S. P., Lindblad-Toh, K., Wade, C. M., Mikkelsen, T. S., Karlsson, E. K., Jaffe, D. B., Kamal, M., Clamp, M., Chang, J. L., Kulbokas, E. J., et al. (2005) · Nature · doi:10.1038/nature04338 · Cited by 2,568
GMAP: A genomic mapping and alignment program for mRNA and EST sequences
Wu, T. D., & Watanabe, C. K. (2005) · Bioinformatics · doi:10.1093/bioinformatics/bti310 · Cited by 2,354
BLAST: at the core of a powerful and diverse set of sequence analysis tools
McGinnis, S., & Madden, T. L. (2004) · Nucleic Acids Research · doi:10.1093/nar/gkh435 · Cited by 2,169
Genome sequence of the Brown Norway rat yields insights into mammalian evolution
Rat Genome Sequencing Project Consortium, DNA sequencing: Baylor College of Medicine, Gibbs, R. A., Weinstock, G. M., Metzker, M. L., Muzny, D. M., Sodergren, E. J., Scherer, S., Scott, G., Steffen, D., et al. (2004) · Nature · doi:10.1038/nature02426 · Cited by 2,164
Self-citationDatabase resources of the National Center for Biotechnology Information
(2016) · Nucleic Acids Research · doi:10.1093/nar/gkv1290 · Cited by 1,470
Adaptive seeds tame genomic sequence comparison
Kiełbasa, S. M., Wan, R., Sato, K., Horton, P., & Frith, M. C. (2011) · Genome Research · doi:10.1101/gr.113985.110 · Cited by 1,281
Human–Mouse Alignments with BLASTZ
Schwartz, S., Kent, W. J., Smit, A., Zhang, Z., Baertsch, R., Hardison, R. C., Haussler, D., & Miller, W. (2003) · Genome Research · doi:10.1101/gr.809403 · Cited by 1,239
Database resources of the National Center for Biotechnology
Wheeler, D. L. (2003) · Nucleic Acids Research · doi:10.1093/nar/gkg033 · Cited by 1,109
Li, M., Chen, X., Li, X., Ma, B., & Vitanyi, P. M. B. (2004) · IEEE Transactions on Information Theory · doi:10.1109/tit.2004.838101 · Cited by 1,062
Self-citationDatabase resources of the National Center for Biotechnology Information
Wheeler, D. L., Barrett, T., Benson, D. A., Bryant, S. H., Canese, K., Chetvernin, V., Church, D. M., DiCuccio, M., Edgar, R., Federhen, S., et al. (2007) · Nucleic Acids Research · doi:10.1093/nar/gkm1000 · Cited by 1,007
A survey of sequence alignment algorithms for next-generation sequencing
Li, H., & Homer, N. (2010) · Briefings in Bioinformatics · doi:10.1093/bib/bbq015 · Cited by 875
The Selaginella Genome Identifies Genetic Changes Associated with the Evolution of Vascular Plants
Banks, J. A., Nishiyama, T., Hasebe, M., Bowman, J. L., Gribskov, M., dePamphilis, C., Albert, V. A., Aono, N., Aoyama, T., Ambrose, B. A., et al. (2011) · Science · doi:10.1126/science.1203810 · Cited by 868
Database resources of the National Center for Biotechnology Information
Coordinators, N. R. (2012) · Nucleic Acids Research · doi:10.1093/nar/gks1189 · Cited by 854
Database resources of the National Center for Biotechnology Information
Sayers, E. W., Barrett, T., Benson, D. A., Bolton, E., Bryant, S. H., Canese, K., Chetvernin, V., Church, D. M., DiCuccio, M., Federhen, S., et al. (2010) · Nucleic Acids Research · doi:10.1093/nar/gkp967 · Cited by 804
Database resources of the National Center for Biotechnology Information
Wheeler, D. L., Barrett, T., Benson, D. A., Bryant, S. H., Canese, K., Chetvernin, V., Church, D. M., DiCuccio, M., Edgar, R., Federhen, S., et al. (2007) · Nucleic Acids Research · doi:10.1093/nar/gkl1031 · Cited by 734
Genome of the marsupial Monodelphis domestica reveals innovation in non-coding sequences
Broad Institute Genome Sequencing Platform, Mikkelsen, T. S., Broad Institute Whole Genome Assembly Team, Wakefield, M. J., Aken, B., Amemiya, C. T., Chang, J. L., Duke, S., Garber, M., Gentles, A. J., et al. (2007) · Nature · doi:10.1038/nature05805 · Cited by 711
Database resources of the National Center for Biotechnology Information
Sayers, E. W., Barrett, T., Benson, D. A., Bolton, E., Bryant, S. H., Canese, K., Chetvernin, V., Church, D. M., DiCuccio, M., Federhen, S., et al. (2011) · Nucleic Acids Research · doi:10.1093/nar/gkq1172 · Cited by 638
DNA sequence and analysis of human chromosome 9
Humphray, S. J., Oliver, K., Hunt, A. R., Plumb, R. W., Loveland, J. E., Howe, K. L., Andrews, T. D., Searle, S., Hunt, S. E., Scott, C. E., et al. (2004) · Nature · doi:10.1038/nature02465 · Cited by 637
SHRiMP: Accurate Mapping of Short Color-space Reads
Rumble, S. M., Lacroute, P., Dalca, A. V., Fiume, M., Sidow, A., & Brudno, M. (2009) · PLoS Computational Biology · doi:10.1371/journal.pcbi.1000386 · Cited by 575
A review of methods and databases for metagenomic classification and assembly
Breitwieser, F. P., Lu, J., & Salzberg, S. L. (2019) · Briefings in Bioinformatics · doi:10.1093/bib/bbx120 · Cited by 566
BFAST: An Alignment Tool for Large Scale Genome Resequencing
Homer, N., Merriman, B., & Nelson, S. F. (2009) · PLoS ONE · doi:10.1371/journal.pone.0007767 · Cited by 529
Database resources of the National Center for Biotechnology Information
Sayers, E. W., Barrett, T., Benson, D. A., Bolton, E., Bryant, S. H., Canese, K., Chetvernin, V., Church, D. M., DiCuccio, M., Federhen, S., et al. (2012) · Nucleic Acids Research · doi:10.1093/nar/gkr1184 · Cited by 523
De novo assembly of haplotype-resolved genomes with trio binning
Koren, S., Rhie, A., Walenz, B. P., Dilthey, A. T., Bickhart, D. M., Kingan, S. B., Hiendleder, S., Williams, J. L., Smith, T. P. L., & Phillippy, A. M. (2018) · Nature Biotechnology · doi:10.1038/nbt.4277 · Cited by 522
Reducing storage requirements for biological sequence comparison
Roberts, M., Hayes, W., Hunt, B. R., Mount, S. M., & Yorke, J. A. (2004) · Bioinformatics · doi:10.1093/bioinformatics/bth408 · Cited by 485
The genome of flax (Linum usitatissimum) assembled de novo from short shotgun sequence reads
Wang, Z., Hobson, N., Galindo, L., Zhu, S., Shi, D., McDill, J., Yang, L., Hawkins, S., Neutelings, G., Datla, R., et al. (2012) · The Plant Journal · doi:10.1111/j.1365-313x.2012.05093.x · Cited by 448
Database resources of the National Center for Biotechnology Information
Wheeler, D. L. (2004) · Nucleic Acids Research · doi:10.1093/nar/gki062 · Cited by 407
Database resources of the National Center for Biotechnology Information
Coordinators, N. R. (2015) · Nucleic Acids Research · doi:10.1093/nar/gku1130 · Cited by 397
Fast and sensitive mapping of nanopore sequencing reads with GraphMap
Sović, I., Šikić, M., Wilm, A., Fenlon, S. N., Chen, S., & Nagarajan, N. (2016) · Nature Communications · doi:10.1038/ncomms11307 · Cited by 393
Database resources of the National Center for Biotechnology Information
(2014) · Nucleic Acids Research · doi:10.1093/nar/gkt1146 · Cited by 384
YASS: enhancing the sensitivity of DNA similarity search
Noe, L., & Kucherov, G. (2005) · Nucleic Acids Research · doi:10.1093/nar/gki478 · Cited by 374
Database resources of the National Center for Biotechnology Information
Wheeler, D. L. (2006) · Nucleic Acids Research · doi:10.1093/nar/gkj158 · Cited by 370
Genome rearrangements in mammalian evolution: lessons from human and mouse genomes
Pevzner, P., & Tesler, G. (2003) · Genome Research · doi:10.1101/gr.757503 · Cited by 369
Sense from sequence reads: methods for alignment and assembly
Flicek, P., & Birney, E. (2009) · Nature Methods · doi:10.1038/nmeth.1376 · Cited by 358
Mammalian phylogenomics comes of age
Murphy, W. J., Pevzner, P. A., & O'Brien, S. J. (2004) · Trends in Genetics · doi:10.1016/j.tig.2004.09.005 · Cited by 349
Barker, M. S., Kane, N. C., Matvienko, M., Kozik, A., Michelmore, R. W., Knapp, S. J., & Rieseberg, L. H. (2008) · Molecular Biology and Evolution · doi:10.1093/molbev/msn187 · Cited by 345
Using quality scores and longer reads improves accuracy of Solexa read mapping
Smith, A. D., Xuan, Z., & Zhang, M. Q. (2008) · BMC Bioinformatics · doi:10.1186/1471-2105-9-128 · Cited by 333
Græmlin: General and robust alignment of multiple large interaction networks
Flannick, J., Novak, A., Srinivasan, B. S., McAdams, H. H., & Batzoglou, S. (2006) · Genome Research · doi:10.1101/gr.5235706 · Cited by 320
Salmonella enterica genomes from victims of a major sixteenth-century epidemic in Mexico
Vågene, Å. J., Herbig, A., Campana, M. G., Robles García, N. M., Warinner, C., Sabin, S., Spyrou, M. A., Andrades Valtueña, A., Huson, D., Tuross, N., et al. (2018) · Nature Ecology & Evolution · doi:10.1038/s41559-017-0446-6 · Cited by 316
WindowMasker: window-based masker for sequenced genomes
Morgulis, A., Gertz, E. M., Schäffer, A. A., & Agarwala, R. (2006) · Bioinformatics · doi:10.1093/bioinformatics/bti774 · Cited by 311
Genome-wide synteny through highly sensitive sequence alignment: Satsuma
Grabherr, M. G., Russell, P., Meyer, M., Mauceli, E., Alföldi, J., Di Palma, F., & Lindblad-Toh, K. (2010) · Bioinformatics · doi:10.1093/bioinformatics/btq102 · Cited by 287
Strategies and tools for whole-genome alignments
Couronne, O., Poliakov, A., Bray, N., Ishkhanov, T., Ryaboy, D., Rubin, E., Pachter, L., & Dubchak, I. (2003) · Genome Research · doi:10.1101/gr.762503 · Cited by 224
Genome variation in Cryptococcus gattii, an emerging pathogen of immunocompetent hosts
D’Souza, C. A., Kronstad, J. W., Taylor, G., Warren, R., Yuen, M., Hu, G., Jung, W. H., Sham, A., Kidd, S. E., Tangen, K., et al. (2011) · mBio · doi:10.1128/mbio.00342-10 · Cited by 202
Technology dictates algorithms: recent developments in read alignment
Alser, M., Rotman, J., Deshpande, D., Taraszka, K., Shi, H., Baykal, P. I., Yang, H. T., Xue, V., Knyazev, S., Singer, B. D., et al. (2021) · Genome Biology · doi:10.1186/s13059-021-02443-7 · Cited by 144
Multiple genome alignment in the telomere-to-telomere assembly era
Kille, B., Balaji, A., Sedlazeck, F. J., Nute, M., & Treangen, T. J. (2022) · Genome Biology · doi:10.1186/s13059-022-02735-6 · Cited by 47
Murasaki: A Fast, Parallelizable Algorithm to Find Anchors from Multiple Genomes
Popendorf, K., Tsuyoshi, H., Osana, Y., & Sakakibara, Y. (2010) · PLoS ONE · doi:10.1371/journal.pone.0012651 · Cited by 32
“Newer algorithms like FASTA [2] and later BLAST [3] and its derivatives (PatternHunter, BLASTZ, Mauve, etc.) rely on subsequences of unusually high conservation to ‘‘anchor’’ a search to a smaller area where a more detailed homology search can be conducted in reasonable time, from which the term anchor is derived.”
BackgroundInfluentialApplication of a superword array in genome assembly
Huang, X. (2006) · Nucleic Acids Research · doi:10.1093/nar/gkj419 · Cited by 30
Whole-Genome Alignment: Methods, Challenges, and Future Directions
Saada, B., Zhang, T., Siga, E., Zhang, J., & Magalhães Muniz, M. M. (2024) · Applied Sciences · doi:10.3390/app14114837 · Cited by 15
Metadata
- Authors
- Ma, B., Tromp, J., & Li, M.
- Venue
- Bioinformatics
- Publisher
- Oxford University Press (OUP)
- Published
- 2002-03-01
- Volume
- 18
- Issue
- 3
- Pages
- 440-445
- ISSN
- 1367-4803 (ISSN-L)
- 1367-4811
- OpenAlex
- W2128591967
- Cited by
- 829
- References
- 12
- FWCI
- 14.79
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.