{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T16:03:45Z","timestamp":1774368225852,"version":"3.50.1"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"1","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2010,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:sec>\n            <jats:title>Background<\/jats:title>\n            <jats:p>Tandem mass spectrometry-based database searching has become an important technology for peptide and protein identification. One of the key challenges in database searching is the remarkable increase in computational demand, brought about by the expansion of protein databases, semi- or non-specific enzymatic digestion, post-translational modifications and other factors. Some software tools choose peptide indexing to accelerate processing. However, peptide indexing requires a large amount of time and space for construction, especially for the non-specific digestion. Additionally, it is not flexible to use.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Results<\/jats:title>\n            <jats:p>We developed an algorithm based on the longest common prefix (ABLCP) to efficiently organize a protein sequence database. The longest common prefix is a data structure that is always coupled to the suffix array. It eliminates redundant candidate peptides in databases and reduces the corresponding peptide-spectrum matching times, thereby decreasing the identification time. This algorithm is based on the property of the longest common prefix. Even enzymatic digestion poses a challenge to this property, but some adjustments can be made to this algorithm to ensure that no candidate peptides are omitted. Compared with peptide indexing, ABLCP requires much less time and space for construction and is subject to fewer restrictions.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Conclusions<\/jats:title>\n            <jats:p>The ABLCP algorithm can help to improve data analysis efficiency. A software tool implementing this algorithm is available at <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"http:\/\/pfind.ict.ac.cn\/pfind2dot5\/index.htm\" ext-link-type=\"uri\">http:\/\/pfind.ict.ac.cn\/pfind2dot5\/index.htm<\/jats:ext-link>\n            <\/jats:p>\n          <\/jats:sec>","DOI":"10.1186\/1471-2105-11-577","type":"journal-article","created":{"date-parts":[[2010,11,25]],"date-time":"2010-11-25T19:15:03Z","timestamp":1290712503000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Speeding up tandem mass spectrometry-based database searching by longest common prefix"],"prefix":"10.1186","volume":"11","author":[{"given":"Chen","family":"Zhou","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hao","family":"Chi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Le-Heng","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"You","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yan-Jie","family":"Wu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yan","family":"Fu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rui-Xiang","family":"Sun","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Si-Min","family":"He","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2010,11,25]]},"reference":[{"key":"4160_CR1","doi-asserted-by":"publisher","first-page":"976","DOI":"10.1016\/1044-0305(94)80016-2","volume":"5","author":"JK Eng","year":"1994","unstructured":"Eng JK, McCormack AL, Yates Iii JR: An approach to correlate tandem mass spectral data of peptides with amino acid sequences in a protein database. Journal of the American Society for Mass Spectrometry 1994, 5: 976\u2013989. 10.1016\/1044-0305(94)80016-2","journal-title":"Journal of the American Society for Mass Spectrometry"},{"key":"4160_CR2","doi-asserted-by":"publisher","first-page":"3551","DOI":"10.1002\/(SICI)1522-2683(19991201)20:18<3551::AID-ELPS3551>3.0.CO;2-2","volume":"20","author":"DN Perkins","year":"1999","unstructured":"Perkins DN, Pappin DJC, Creasy DM, Cottrell JS: Probability-based protein identification by searching sequence databases using mass spectrometry data. Electrophoresis 1999, 20: 3551\u20133567. 10.1002\/(SICI)1522-2683(19991201)20:18<3551::AID-ELPS3551>3.0.CO;2-2","journal-title":"Electrophoresis"},{"key":"4160_CR3","doi-asserted-by":"publisher","first-page":"1466","DOI":"10.1093\/bioinformatics\/bth092","volume":"20","author":"R Craig","year":"2004","unstructured":"Craig R, Beavis RC: TANDEM: matching proteins with tandem mass spectra. BIOINFORMATICS 2004, 20: 1466\u20131467. 10.1093\/bioinformatics\/bth092","journal-title":"BIOINFORMATICS"},{"key":"4160_CR4","doi-asserted-by":"publisher","first-page":"958","DOI":"10.1021\/pr0499491","volume":"3","author":"LY Geer","year":"2004","unstructured":"Geer LY, Markey SP, Kowalak JA, Wagner L, Xu M, Maynard DM, Yang X, Shi W, Bryant SH: Open mass spectrometry search algorithm. Journal of proteome research 2004, 3: 958\u2013964. 10.1021\/pr0499491","journal-title":"Journal of proteome research"},{"key":"4160_CR5","doi-asserted-by":"publisher","first-page":"1454","DOI":"10.1002\/pmic.200300485","volume":"3","author":"J Colinge","year":"2003","unstructured":"Colinge J, Masselot A, Giron M, Dessingy T, Magnin J: OLAV: towards high-throughput tandem mass spectrometry data identification. Proteomics 2003, 3: 1454\u20131463. 10.1002\/pmic.200300485","journal-title":"Proteomics"},{"key":"4160_CR6","doi-asserted-by":"publisher","first-page":"3016","DOI":"10.1093\/bioinformatics\/btm417","volume":"23","author":"FF Roos","year":"2007","unstructured":"Roos FF, Jacob R, Grossmann J, Fischer B, Buhmann JM, Gruissem W, Baginsky S, Widmayer P: PepSplice: cache-efficient search algorithms for comprehensive identification of tandem mass spectra. Bioinformatics 2007, 23: 3016\u20133023. 10.1093\/bioinformatics\/btm417","journal-title":"Bioinformatics"},{"key":"4160_CR7","doi-asserted-by":"publisher","first-page":"3022","DOI":"10.1021\/pr800127y","volume":"7","author":"CY Park","year":"2008","unstructured":"Park CY, K ll L, Klammer AA, MacCoss MJ, Noble WS: Rapid and accurate peptide identification from tandem mass spectra. Journal of proteome research 2008, 7: 3022. 10.1021\/pr800127y","journal-title":"Journal of proteome research"},{"key":"4160_CR8","doi-asserted-by":"publisher","first-page":"1948","DOI":"10.1093\/bioinformatics\/bth186","volume":"20","author":"Y Fu","year":"2004","unstructured":"Fu Y, Yang Q, Sun R, Li D, Zeng R, Ling CX, Gao W: Exploiting the kernel trick to correlate fragment ions for peptide identification via tandem mass spectrometry. Bioinformatics 2004, 20: 1948\u20131954. 10.1093\/bioinformatics\/bth186","journal-title":"Bioinformatics"},{"key":"4160_CR9","doi-asserted-by":"publisher","first-page":"3049","DOI":"10.1093\/bioinformatics\/bti439","volume":"21","author":"D Li","year":"2005","unstructured":"Li D, Fu Y, Sun R, Ling CX, Wei Y, Zhou H, Zeng R, Yang Q, He S, Gao W: pFind: a novel database-searching software system for automated peptide and protein identification via tandem mass spectrometry. Bioinformatics 2005, 21: 3049\u20133050. 10.1093\/bioinformatics\/bti439","journal-title":"Bioinformatics"},{"key":"4160_CR10","doi-asserted-by":"publisher","first-page":"2985","DOI":"10.1002\/rcm.3173","volume":"21","author":"L Wang","year":"2007","unstructured":"Wang L, Li DQ, Fu Y, Wang HP, Zhang JF, Yuan ZF, Sun RX, Zeng R, He SM, Gao W: pFind 2.0: a software package for peptide and protein identification via tandem mass spectrometry. Rapid Communications in Mass Spectrometry 2007, 21: 2985\u20132991. 10.1002\/rcm.3173","journal-title":"Rapid Communications in Mass Spectrometry"},{"key":"4160_CR11","doi-asserted-by":"publisher","first-page":"1985","DOI":"10.1002\/pmic.200300721","volume":"4","author":"PJ Kersey","year":"2004","unstructured":"Kersey PJ, Duarte J, Williams A, Karavidopoulou Y, Birney E, Apweiler R: Technical Brief The International Protein Index: An integrated database for proteomics experiments. Proteomics 2004, 4: 1985\u20131988. 10.1002\/pmic.200300721","journal-title":"Proteomics"},{"key":"4160_CR12","doi-asserted-by":"publisher","first-page":"3931","DOI":"10.1021\/ac0481046","volume":"77","author":"H Wilfred","year":"2005","unstructured":"Wilfred H, Tang BRH, Ignat ShilovV, Sean SeymourL, Sean KeatingP, Alex Loboda, Alpesh PatelA, Daniel SchaefferA, Lydia NuwaysirM: Discovering Known and Unanticipated Protein Modifications Using MS\/MS Database Searching. Analytical Chemistry 2005, 77: 3931\u20133946. 10.1021\/ac0481046","journal-title":"Analytical Chemistry"},{"key":"4160_CR13","volume-title":"Bioinformatics","author":"B Lu","year":"2003","unstructured":"Lu B, Chen T: A suffix tree approach to the interpretation of tandem mass spectra: applications to peptides of non-specific digestion and post-translational modifications. Bioinformatics 2003., 19: 10.1093\/bioinformatics\/btg1068"},{"key":"4160_CR14","doi-asserted-by":"publisher","first-page":"4626","DOI":"10.1021\/ac050102d","volume":"77","author":"S Tanner","year":"2005","unstructured":"Tanner S, Shu H, Frank A, Wang LC, Zandi E, Mumby M, Pevzner PA, Bafna V: InsPecT: identification of posttranslationally modified peptides from tandem mass spectra. Anal Chem 2005, 77: 4626\u20134639. 10.1021\/ac050102d","journal-title":"Anal Chem"},{"key":"4160_CR15","doi-asserted-by":"publisher","first-page":"230","DOI":"10.1007\/978-3-540-30219-3_20","volume-title":"Algorithms in Bioinformatics","author":"N Edwards","year":"2004","unstructured":"Edwards N, Lippert R: Sequence database compression for peptide identification from tandem mass spectra. Algorithms in Bioinformatics 2004, 230\u2013241. full_text"},{"key":"4160_CR16","volume-title":"Molecular Systems Biology","author":"NJ Edwards","year":"2007","unstructured":"Edwards NJ: Novel peptide identification from tandem mass spectra using ESTs and sequence database compression. Molecular Systems Biology 2007., 3:"},{"key":"4160_CR17","first-page":"68","volume-title":"Lecture Notes in Computer Science","author":"N Edwards","year":"2002","unstructured":"Edwards N, Lippert R: Generating peptide candidates from amino-acid sequence databases for protein identification via mass spectrometry. Lecture Notes in Computer Science 2002, 68\u201381. full_text"},{"key":"4160_CR18","doi-asserted-by":"crossref","unstructured":"Li Y, Chi H, Wang LH, Wang HP, Fu Y, Yuan ZF, Li SJ, Liu YS, Sun RX, Zeng R, He SM: Speeding up tandem mass spectrometry based database searching by peptide and spectrum indexing. Rapid Commun Mass Spectrom 24: 807\u2013814. 10.1002\/rcm.4448","DOI":"10.1002\/rcm.4448"},{"key":"4160_CR19","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1021\/pr070244j","volume":"7","author":"J Klimek","year":"2008","unstructured":"Klimek J, Eddes JS, Hohmann L, Jackson J, Peterson A, Letarte S, Gafken PR, Katz JE, Mallick P, Lee H: The Standard Protein Mix Database: A Diverse Dataset to Assist in the Production of Improved Peptide and Protein Identification Software Tools. Journal of proteome research 2008, 7: 96. 10.1021\/pr070244j","journal-title":"Journal of proteome research"},{"key":"4160_CR20","doi-asserted-by":"publisher","first-page":"1488","DOI":"10.1073\/pnas.0609836104","volume":"104","author":"J Vill\u00e9n","year":"2007","unstructured":"Vill\u00e9n J, Beausoleil SA, Gerber SA, Gygi SP: Large-scale phosphorylation analysis of mouse liver. Proceedings of the National Academy of Sciences 2007, 104: 1488. 10.1073\/pnas.0609836104","journal-title":"Proceedings of the National Academy of Sciences"},{"key":"4160_CR21","first-page":"31","volume":"39","author":"J Simon","year":"2007","unstructured":"Simon J, Puglisi WFS, Anderw H, Turpin Simon J: A Taxonomy of Suffix Array Construction Algorithms. ACM Computing Surveys 2007, 39: 31.","journal-title":"ACM Computing Surveys"},{"key":"4160_CR22","first-page":"319","volume-title":"Society for Industrial and Applied Mathematics Philadelphia, PA, USA","author":"U Manber","year":"1990","unstructured":"Manber U, Myers G: Suffix arrays: A new method for on-line string searches. Society for Industrial and Applied Mathematics Philadelphia, PA, USA 1990, 319\u2013327."},{"key":"4160_CR23","volume-title":"Cambridge Univ Pr","author":"D Gusfield","year":"1997","unstructured":"Gusfield D: Algorithms on strings, trees, and sequences: computer science and computational biology. Cambridge Univ Pr 1997."},{"key":"4160_CR24","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1016\/j.tcs.2007.07.017","volume":"387","author":"NJ Larsson","year":"2007","unstructured":"Larsson NJ, Sadakane K: Faster suffix sorting. Theoretical Computer Science 2007, 387: 258\u2013272.","journal-title":"Theoretical Computer Science"},{"key":"4160_CR25","doi-asserted-by":"publisher","first-page":"936","DOI":"10.1145\/1217856.1217858","volume":"53","author":"J K\u00e4rkk\u00e4inen","year":"2006","unstructured":"K\u00e4rkk\u00e4inen J, Sanders P, Burkhardt S: Linear work suffix array construction. Journal of the ACM (JACM) 2006, 53: 936. 10.1145\/1217856.1217858","journal-title":"Journal of the ACM (JACM)"},{"key":"4160_CR26","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/s00453-004-1094-1","volume":"40","author":"G Manzini","year":"2004","unstructured":"Manzini G, Ferragina P: Engineering a lightweight suffix array construction algorithm. Algorithmica 2004, 40: 33\u201350. 10.1007\/s00453-004-1094-1","journal-title":"Algorithmica"},{"key":"4160_CR27","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1227161.1278374","volume":"12","author":"MA Maniscalco","year":"2008","unstructured":"Maniscalco MA, Puglisi SJ: An efficient, versatile approach to suffix sorting. Journal of Experimental Algorithmics (JEA) 2008, 12: 1\u20132. 10.1145\/1227161.1278374","journal-title":"Journal of Experimental Algorithmics (JEA)"},{"key":"4160_CR28","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/3-540-48194-X_17","volume":"2089","author":"T Kasai","year":"2001","unstructured":"Kasai T, Lee G, Arimura H, Arikawa S, Park K: Linear-time longest-common-prefix computation in suffix arrays and its applications. Lecture Notes in Computer Science 2001, 2089: 181\u2013192. full_text","journal-title":"Lecture Notes in Computer Science"},{"key":"4160_CR29","first-page":"124","volume-title":"Springer","author":"SJ Puglisi","year":"2008","unstructured":"Puglisi SJ, Turpin A: Space-time tradeoffs for Longest-Common-Prefix array computation. Springer 2008, 124\u2013135."},{"key":"4160_CR30","first-page":"340","volume":"18","author":"AV Aho","year":"1975","unstructured":"Aho AV, Corasick MJ: Efficient string matching: an aid to bibliographic search. Communications of the ACM 1975, 18: 340.","journal-title":"Communications of the ACM"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-11-577.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T05:18:13Z","timestamp":1630473493000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-11-577"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,11,25]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2010,12]]}},"alternative-id":["4160"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-11-577","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,11,25]]},"assertion":[{"value":"10 July 2010","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 November 2010","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 November 2010","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"577"}}