{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T06:28:43Z","timestamp":1743143323996,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":39,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642200359"},{"type":"electronic","value":"9783642200366"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-20036-6_27","type":"book-chapter","created":{"date-parts":[[2011,3,23]],"date-time":"2011-03-23T22:49:24Z","timestamp":1300920564000},"page":"298-319","source":"Crossref","is-referenced-by-count":4,"title":["Blocked Pattern Matching Problem and Its Applications in Proteomics"],"prefix":"10.1007","author":[{"given":"Julio","family":"Ng","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amihood","family":"Amir","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pavel A.","family":"Pevzner","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"5","key":"27_CR1","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1371\/journal.pbio.0040127","volume":"4","author":"F. Abascal","year":"2006","unstructured":"Abascal, F., Posada, D., Knight, R.D., Zardoya, R.: Parallel evolution of the genetic code in arthropod mitochondrial genomes. PLoS Biol.\u00a04(5), e127 (2006)","journal-title":"PLoS Biol."},{"key":"27_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/11780441_1","volume-title":"Combinatorial Pattern Matching","author":"A. Amir","year":"2006","unstructured":"Amir, A.: Asynchronous pattern matching. In: Lewenstein, M., Valiente, G. (eds.) CPM 2006. LNCS, vol.\u00a04009, pp. 1\u201310. Springer, Heidelberg (2006)"},{"key":"27_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/978-3-540-75530-2_4","volume-title":"String Processing and Information Retrieval","author":"A. Amir","year":"2007","unstructured":"Amir, A., Aumann, Y., Indyk, P., Levy, A., Porat, E.: Efficient computations of \u21131 and \u2113\u2009\u221e\u2009 rearrangement distances. In: Ziviani, N., Baeza-Yates, R. (eds.) SPIRE 2007. LNCS, vol.\u00a04726, pp. 39\u201349. Springer, Heidelberg (2007)"},{"key":"27_CR4","doi-asserted-by":"crossref","unstructured":"Amir, A., Aumann, Y., Benson, G., Levy, A., Lipsky, O., Porat, E., Skiena, S., Vishne, U.: Pattern matching with address errors: rearrangement distances. In: Proc. 17th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1221\u20131229 (2006)","DOI":"10.1145\/1109557.1109692"},{"key":"27_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1007\/978-3-540-69068-9_13","volume-title":"Combinatorial Pattern Matching","author":"A. Amir","year":"2008","unstructured":"Amir, A., Aumann, Y., Kapah, O., Levy, A., Porat, E.: Approximate string matching with address bit errors. In: Ferragina, P., Landau, G.M. (eds.) CPM 2008. LNCS, vol.\u00a05029, pp. 118\u2013129. Springer, Heidelberg (2008)"},{"key":"27_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1007\/978-3-642-16321-0_41","volume-title":"String Processing and Information Retrieval","author":"A. Amir","year":"2010","unstructured":"Amir, A., Eisenberg, E., Keller, O., Levy, A., Porat, E.: Approximate string matching with stuck address bits. In: Chavez, E., Lonardi, S. (eds.) SPIRE 2010. LNCS, vol.\u00a06393, pp. 395\u2013405. Springer, Heidelberg (2010)"},{"key":"27_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/978-3-540-75520-3_11","volume-title":"Algorithms \u2013 ESA 2007","author":"A. Amir","year":"2007","unstructured":"Amir, A., Hartman, T., Kapah, O., Levy, A., Porat, E.: On the cost of interchange rearrangement in strings. In: Arge, L., Hoffmann, M., Welzl, E. (eds.) ESA 2007. LNCS, vol.\u00a04698, pp. 99\u2013110. Springer, Heidelberg (2007)"},{"key":"27_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/978-3-540-73437-6_20","volume-title":"Combinatorial Pattern Matching","author":"A. Amir","year":"2007","unstructured":"Amir, A., Kapah, O., Porat, E.: Deterministic length reduction: Fast convolution in sparse data and applications. In: Ma, B., Zhang, K. (eds.) CPM 2007. LNCS, vol.\u00a04580, pp. 183\u2013194. Springer, Heidelberg (2007)"},{"key":"27_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1007\/978-3-540-27801-6_30","volume-title":"Combinatorial Pattern Matching","author":"R. Baeza-Yates","year":"2004","unstructured":"Baeza-Yates, R.: A fast set intersection algorithm for sorted sequences. In: Sahinalp, S., Muthukrishnan, S., Dogrusoz, U. (eds.) CPM 2004. LNCS, vol.\u00a03109, pp. 400\u2013408. Springer, Heidelberg (2004)"},{"issue":"12","key":"27_CR10","doi-asserted-by":"publisher","first-page":"2607","DOI":"10.1093\/nar\/29.12.2607","volume":"29","author":"J. Besemer","year":"2001","unstructured":"Besemer, J., Lomsadze, A., Borodovsky, M.: Genemarks: a self-training method for prediction of gene starts in microbial genomes implications for finding sequence motifs in regulatory regions. Nucleic Acids Research\u00a029(12), 2607\u20132618 (2001)","journal-title":"Nucleic Acids Research"},{"key":"27_CR11","doi-asserted-by":"crossref","unstructured":"Cardoze, D.E., Schulman, L.J.: Pattern matching for spatial point sets. In: Proc. 39th Annu. IEEE Sympos. Found. Comput. Sci., pp. 156\u2013165 (1998)","DOI":"10.1109\/SFCS.1998.743439"},{"issue":"52","key":"27_CR12","doi-asserted-by":"publisher","first-page":"21034","DOI":"10.1073\/pnas.0811066106","volume":"105","author":"N.E. Castellana","year":"2008","unstructured":"Castellana, N.E., Payne, S.H., Shen, Z., Stanke, M., Bafna, V., Briggs, S.P.: Discovery and revision of arabidopsis genes by proteogenomics. Proceedings of the National Academy of Sciences\u00a0105(52), 21034\u201321038 (2008)","journal-title":"Proceedings of the National Academy of Sciences"},{"key":"27_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1007\/978-3-642-12200-2_22","volume-title":"LATIN 2010: Theoretical Informatics","author":"H. Cohen","year":"2010","unstructured":"Cohen, H., Porat, E.: Fast set intersection and two-patterns matching. In: L\u00f3pez-Ortiz, A. (ed.) LATIN 2010. LNCS, vol.\u00a06034, pp. 234\u2013242. Springer, Heidelberg (2010)"},{"issue":"6","key":"27_CR14","doi-asserted-by":"publisher","first-page":"1761","DOI":"10.1137\/S0097539700370527","volume":"31","author":"R. Cole","year":"2002","unstructured":"Cole, R., Hariharan, R.: Approximate string matching: A simpler faster algorithm. SIAM J. Comput.\u00a031(6), 1761\u20131782 (2002)","journal-title":"SIAM J. Comput."},{"key":"27_CR15","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L.: Introduction to Algorithms. MIT Press and McGraw-Hill (1992)"},{"key":"27_CR16","unstructured":"Demaine, E.D., L\u00f3pez-Ortiz, A., Munro, I.J.: Adaptive set intersections, unions and differences. In: Proc. 11th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 743\u2013752 (2000)"},{"issue":"2","key":"27_CR17","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1007\/BF01293666","volume":"14","author":"P. Dietz","year":"1993","unstructured":"Dietz, P., Mehlhorn, K., Raman, R., Uhrig, C.: Lower bounds for set intersection queries. Algorithmica\u00a014(2), 154\u2013168 (1993)","journal-title":"Algorithmica"},{"issue":"19","key":"27_CR18","doi-asserted-by":"publisher","first-page":"7402","DOI":"10.1073\/pnas.0506514103","volume":"103","author":"K.S.J. Elenitoba-Johnson","year":"2006","unstructured":"Elenitoba-Johnson, K.S.J., Crockett, D.K., Schumacher, J.A., Jenson, S.D., Coffin, C.M., Rockwood, A.L., Lim, M.S.: Proteomic identification of oncogenic chromosomal translocation partners encoding chimeric anaplastic lymphoma kinase fusion proteins. Proceedings of the National Academy of Sciences\u00a0103(19), 7402\u20137407 (2006)","journal-title":"Proceedings of the National Academy of Sciences"},{"issue":"11","key":"27_CR19","doi-asserted-by":"publisher","first-page":"976","DOI":"10.1016\/1044-0305(94)80016-2","volume":"5","author":"J. Eng","year":"1994","unstructured":"Eng, J., McCormack, A., Yates, J.: 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\u00a05(11), 976\u2013989 (1994)","journal-title":"Journal of the American Society for Mass Spectrometry"},{"key":"27_CR20","doi-asserted-by":"publisher","first-page":"964","DOI":"10.1021\/ac048788h","volume":"77","author":"A.M. Frank","year":"2005","unstructured":"Frank, A.M., Pevzner, P.A.: PepNovo: De Novo Peptide Sequencing via Probabilistic Network Modeling. Anal. Chem.\u00a077, 964\u2013973 (2005)","journal-title":"Anal. Chem."},{"key":"27_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1007\/3-540-45784-4","volume-title":"Algorithms in Bioinformatics","author":"R. Guig\u00f3","year":"2002","unstructured":"Guig\u00f3, R., Gusfield, D., Edwards, N., Lippert, R.: Generating peptide candidates from amino-acid sequence databases for protein identification via mass spectrometry. In: Guig\u00f3, R., Gusfield, D. (eds.) WABI 2002. LNCS, vol.\u00a02452, pp. 68\u201381. Springer, Heidelberg (2002)"},{"key":"27_CR22","doi-asserted-by":"publisher","first-page":"1362","DOI":"10.1101\/gr.6427907","volume":"17","author":"N. Gupta","year":"2007","unstructured":"Gupta, N., Tanner, S., Jaitly, N., Adkins, J., Lipton, M., Edwards, R., Romine, M., Osterman, A., Bafna, V., Smith, R., Pevzner, P.: Whole proteome analysis of post-translational modifications: applications of mass-spectrometry for proteogenomic annotation. Genome Res.\u00a017, 1362\u20131377 (2007)","journal-title":"Genome Res."},{"issue":"9","key":"27_CR23","doi-asserted-by":"publisher","first-page":"4173","DOI":"10.1021\/pr9004794","volume":"8","author":"N. Gupta","year":"2009","unstructured":"Gupta, N., Pevzner, P.A.: False discovery rates of protein identifications: A strike against the two-peptide rule. Journal of Proteome Research\u00a08(9), 4173\u20134181 (2009)","journal-title":"Journal of Proteome Research"},{"key":"27_CR24","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on strings, trees, and sequences: computer science and computational biology","author":"D. Gusfield","year":"1997","unstructured":"Gusfield, D.: Algorithms on strings, trees, and sequences: computer science and computational biology. Cambridge University Press, New York (1997)"},{"issue":"8","key":"27_CR25","doi-asserted-by":"publisher","first-page":"1447","DOI":"10.1101\/gr.2674004","volume":"14","author":"J.D. Jaffe","year":"2004","unstructured":"Jaffe, J.D., Stange-Thomann, N., Smith, C., DeCaprio, D., Fisher, S., Butler, J., Calvo, S., Elkins, T., FitzGerald, M.G., Hafez, N., Kodira, C.D., Major, J., Wang, S., Wilkinson, J., Nicol, R., Nusbaum, C., Birren, B., Berg, H.C., Church, G.M.: The complete genome and proteome of mycoplasma mobile. Genome Research\u00a014(8), 1447\u20131461 (2004)","journal-title":"Genome Research"},{"key":"27_CR26","doi-asserted-by":"crossref","unstructured":"Jeong, K., Bandeira, N., Kim, S., Pevzner, P.A.: Gapped spectral dictionaries and their applications for database searches of tandem mass spectra. Mol. Cell. Proteomics (2010) (in press)","DOI":"10.4016\/26771.01"},{"issue":"43","key":"27_CR27","doi-asserted-by":"publisher","first-page":"4315","DOI":"10.1016\/j.tcs.2009.07.013","volume":"410","author":"O. Kapah","year":"2009","unstructured":"Kapah, O., Landau, G.M., Levy, A., Oz, N.: Interchange rearrangement: The element-cost model. Theoretical Computer Science\u00a0410(43), 4315\u20134326 (2009)","journal-title":"Theoretical Computer Science"},{"key":"27_CR28","doi-asserted-by":"publisher","first-page":"1391","DOI":"10.1074\/mcp.M800535-MCP200","volume":"8","author":"S. Kim","year":"2009","unstructured":"Kim, S., Bandeira, N., Pevzner, P.A.: Spectral profiles: A novel representation of tandem mass spectra and its applications for de novo peptide sequencing and identification. Mol. Cell. Proteomics\u00a08, 1391\u20131400 (2009)","journal-title":"Mol. Cell. Proteomics"},{"issue":"1","key":"27_CR29","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1074\/mcp.M800103-MCP200","volume":"8","author":"S. Kim","year":"2009","unstructured":"Kim, S., Gupta, N., Bandeira, N., Pevzner, P.A.: Spectral dictionaries: Integrating de novo peptide sequencing with database search of tandem mass spectra. Mol. Cell. Proteomics\u00a08(1), 53\u201369 (2009)","journal-title":"Mol. Cell. Proteomics"},{"issue":"8","key":"27_CR30","doi-asserted-by":"publisher","first-page":"3354","DOI":"10.1021\/pr8001244","volume":"7","author":"S. Kim","year":"2008","unstructured":"Kim, S., Gupta, N., Pevzner, P.A.: Spectral probabilities and generating functions of tandem mass spectra: A strike against decoy databases. Journal of Proteome Research\u00a07(8), 3354\u20133363 (2008)","journal-title":"Journal of Proteome Research"},{"issue":"1","key":"27_CR31","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1038\/35047500","volume":"2","author":"R.D. Knight","year":"2001","unstructured":"Knight, R.D., Freeland, S.J., Landweber, L.F.: Rewiring the keyboard: evolvability of the genetic code. Nat. Rev. Genet.\u00a02(1), 49\u201358 (2001)","journal-title":"Nat. Rev. Genet."},{"issue":"10","key":"27_CR32","doi-asserted-by":"publisher","first-page":"1660","DOI":"10.1101\/gr.077644.108","volume":"18","author":"G.E. Merrihew","year":"2008","unstructured":"Merrihew, G.E., Davis, C., Ewing, B., Williams, G., K\u00e4ll, L., Frewen, B.E., Noble, W.S., Green, P., Thomas, J.H., MacCoss, M.J.: Use of shotgun proteomics for the identification, confirmation, and correction of c. elegans gene annotations. Genome Research\u00a018(10), 1660\u20131669 (2008)","journal-title":"Genome Research"},{"key":"27_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1007\/3-540-60044-2_50","volume-title":"Combinatorial Pattern Matching","author":"S. Muthukrishnan","year":"1995","unstructured":"Muthukrishnan, S.: New results and open problems related to non-standard stringology. In: Galil, Z., Ukkonen, E. (eds.) CPM 1995. LNCS, vol.\u00a0937, pp. 298\u2013317. Springer, Heidelberg (1995)"},{"issue":"1","key":"27_CR34","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1021\/pr070214g","volume":"7","author":"J. Ng","year":"2008","unstructured":"Ng, J., Pevzner, P.A.: Algorithm for identification of fusion proteins via mass spectrometry. Journal of Proteome Research\u00a07(1), 89\u201395 (2008)","journal-title":"Journal of Proteome Research"},{"issue":"24","key":"27_CR35","doi-asserted-by":"publisher","first-page":"4322","DOI":"10.1093\/bioinformatics\/bti701","volume":"21","author":"P. Nielsen","year":"2005","unstructured":"Nielsen, P., Krogh, A.: Large-scale prokaryotic gene prediction and comparison to genome annotation. Bioinformatics\u00a021(24), 4322\u20134329 (2005)","journal-title":"Bioinformatics"},{"issue":"7","key":"27_CR36","doi-asserted-by":"publisher","first-page":"3022","DOI":"10.1021\/pr800127y","volume":"7","author":"C.Y. Park","year":"2008","unstructured":"Park, C.Y., Klammer, A.A., K\u00e4ll, L., MacCoss, M.J., Noble, W.S.: Rapid and accurate peptide identification from tandem mass spectra. Journal of Proteome Research\u00a07(7), 3022\u20133027 (2008)","journal-title":"Journal of Proteome Research"},{"issue":"9","key":"27_CR37","doi-asserted-by":"publisher","first-page":"1638","DOI":"10.1074\/mcp.T600050-MCP200","volume":"6","author":"I.V. Shilov","year":"2007","unstructured":"Shilov, I.V., Seymour, S.L., Patel, A.A., Loboda, A., Tang, W.H., Keating, S.P., Hunter, C.L., Nuwaysir, L.M., Schaeffer, D.A.: The paragon algorithm, a next generation search engine that uses sequence temperature values and feature probabilities to identify peptides from tandem mass spectra. Molecular & Cellular Proteomics\u00a06(9), 1638\u20131655 (2007)","journal-title":"Molecular & Cellular Proteomics"},{"issue":"14","key":"27_CR38","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, L.C., Zandi, E., Mumby, M., Pevzner, P.A., Bafna, V.: Inspect: Identification of posttranslationally modified peptides from tandem mass spectra. Analytical Chemistry\u00a077(14), 4626\u20134639 (2005)","journal-title":"Analytical Chemistry"},{"issue":"12","key":"27_CR39","doi-asserted-by":"publisher","first-page":"1562","DOI":"10.1038\/nbt1168","volume":"23","author":"D. Tsur","year":"2005","unstructured":"Tsur, D., Tanner, S., Zandi, E., Bafna, V., Pevzner, P.: Identification of post-translational modifications by blind search of mass spectra. Nature Biotechnology\u00a023(12), 1562\u20131567 (2005)","journal-title":"Nature Biotechnology"}],"container-title":["Lecture Notes in Computer Science","Research in Computational Molecular Biology"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-20036-6_27","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,4]],"date-time":"2025-03-04T17:17:13Z","timestamp":1741108633000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-20036-6_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642200359","9783642200366"],"references-count":39,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-20036-6_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}