title: An efficient algorithm for the blocked pattern matching problem.
abstract: BACKGROUND
  Tandem mass spectrometry (MS) has become the method of choice for protein identification and quantification. In the era of big data biology, tandem mass spectra are often searched against huge protein databases generated from genomes or RNA-Seq data for peptide identification. However, most existing tools for MS-based peptide identification compare a tandem mass spectrum against all peptides in a database whose molecular masses are similar to the precursor mass of the spectrum, making mass spectral data analysis slow for huge databases. Tag-based methods extract peptide sequence tags from a tandem mass spectrum and use them as a filter to reduce the number of candidate peptides, thus speeding up the database search. Recently, gapped tags have been introduced into mass spectral data analysis because they improve the sensitivity of peptide identification compared with sequence tags. However, the blocked pattern matching (BPM) problem, which is an essential step in gapped tag-based peptide identification, has not been fully solved.
  
  
  RESULTS
  In this article, we propose a fast and memory-efficient algorithm for the BPM problem. Experiments on both simulated and real datasets showed that the proposed algorithm achieved high speed and high sensitivity for peptide filtration in peptide identification by database search.
  
  
  BACKGROUND
  cswangl@cityu.edu.hk or xwliu@iupui.edu
  
  
  BACKGROUND
  Supplementary data are available at Bioinformatics online.
authors.affiliation: Department of Computer Science, City University of Hong Kong, Kowloon, Hong Kong, Department of BioHealth Informatics, Indiana University-Purdue University Indianapolis and Center for Computational Biology and Bioinformatics, Indiana University School of Medicine, Indianapolis, IN 46202, USA.
authors.forename: Fei
authors.initials: F
authors.lastname: Deng
authors.affiliation: Department of Computer Science, City University of Hong Kong, Kowloon, Hong Kong, Department of BioHealth Informatics, Indiana University-Purdue University Indianapolis and Center for Computational Biology and Bioinformatics, Indiana University School of Medicine, Indianapolis, IN 46202, USA.
authors.forename: Lusheng
authors.initials: L
authors.lastname: Wang
authors.affiliation: Department of Computer Science, City University of Hong Kong, Kowloon, Hong Kong, Department of BioHealth Informatics, Indiana University-Purdue University Indianapolis and Center for Computational Biology and Bioinformatics, Indiana University School of Medicine, Indianapolis, IN 46202, USA Department of Computer Science, City University of Hong Kong, Kowloon, Hong Kong, Department of BioHealth Informatics, Indiana University-Purdue University Indianapolis and Center for Computational Biology and Bioinformatics, Indiana University School of Medicine, Indianapolis, IN 46202, USA.
authors.forename: Xiaowen
authors.initials: X
authors.lastname: Liu
mesh_terms: D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D030562:Databases, Protein; D006801:Humans; D008954:Models, Biological; D010446:Peptide Fragments / Q000737:chemistry*; D010449:Peptide Mapping / Q000379:methods*; D011506:Proteins / Q000737:chemistry*; D020539:Sequence Analysis, Protein / Q000379:methods*; D053719:Tandem Mass Spectrometry / Q000379:methods*
chemical_list: D010446:Peptide Fragments; D011506:Proteins