{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,9]],"date-time":"2024-07-09T11:59:48Z","timestamp":1720526388714},"reference-count":21,"publisher":"Oxford University Press (OUP)","issue":"8","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016,4,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: A palindrome is a string that reads the same forward and backward. Finding palindromic substructures is important in DNA, RNA or protein sequence analysis. We say that two strings of the same length are pal-equivalent if, for each possible centre, they have the same length of the maximal palindrome. Given a text T of length n and a pattern P of length m, we study the palindrome pattern matching problem that finds all indices i such that P and T[i\u2212m+1:i] are pal-equivalent.<\/jats:p>\n               <jats:p>Results: We first solve the online palindrome pattern matching problem in O(m2) preprocessing time and O(mn) query time using O(m2) space. We then extend the problem for multiple patterns and solve the online multiple palindrome pattern matching problem in O(mkM) preprocessing time and O(mkn+c) query time using O(mkM) space, where M is the sum of all pattern lengths, mk is the longest pattern length and c is the number of pattern occurrences.<\/jats:p>\n               <jats:p>Availability and implementation: The source code for all algorithms is freely available at http:\/\/toc.yonsei.ac.kr\/OMPPM<\/jats:p>\n               <jats:p>Contact: \u00a0kimhwee@cs.yonsei.ac.kr<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btv738","type":"journal-article","created":{"date-parts":[[2015,12,18]],"date-time":"2015-12-18T01:47:31Z","timestamp":1450403251000},"page":"1151-1157","source":"Crossref","is-referenced-by-count":7,"title":["OMPPM: online multiple palindrome pattern matching"],"prefix":"10.1093","volume":"32","author":[{"given":"Hwee","family":"Kim","sequence":"first","affiliation":[{"name":"Department of Computer Science, Yonsei University, Seoul 120-749, Republic of Korea"}]},{"given":"Yo-Sub","family":"Han","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Yonsei University, Seoul 120-749, Republic of Korea"}]}],"member":"286","published-online":{"date-parts":[[2015,12,16]]},"reference":[{"key":"2023020112014860700_btv738-B1","doi-asserted-by":"crossref","first-page":"S5","DOI":"10.1093\/bioinformatics\/17.suppl_1.S5","article-title":"An efficient algorithm for finding short approximate non-tandem repeats","volume":"17","author":"Adebiyi","year":"2001","journal-title":"Bioinformatics"},{"key":"2023020112014860700_btv738-B2","doi-asserted-by":"crossref","first-page":"1849","DOI":"10.1093\/bioinformatics\/btg249","article-title":"RVP-net: online prediction of real valued accessible surface area of proteins from single sequences","volume":"19","author":"Ahmad","year":"2003","journal-title":"Bioinformatics"},{"key":"2023020112014860700_btv738-B3","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1145\/360825.360855","article-title":"Efficient string matching: an aid to bibliographic search","volume":"18","author":"Aho","year":"1975","journal-title":"Commun. ACM"},{"key":"2023020112014860700_btv738-B4","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1093\/nar\/gkg091","article-title":"ArrayExpress\u2013a public repository for microarray gene expression data at the EBI","volume":"31","author":"Brazma","year":"2003","journal-title":"Nucleic Acids Res"},{"key":"2023020112014860700_btv738-B5","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1093\/bioinformatics\/17.5.419","article-title":"Efficient large-scale sequence comparison by locality-sensitive hashing","volume":"17","author":"Buhler","year":"2001","journal-title":"Bioinformatics"},{"key":"2023020112014860700_btv738-B6","doi-asserted-by":"crossref","first-page":"226","DOI":"10.1093\/nar\/gks1005","article-title":"Rfam 11.0: 10 years of RNA families","volume":"41","author":"Burge","year":"2013","journal-title":"Nucleic Acids Res"},{"key":"2023020112014860700_btv738-B7","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology","author":"Gusfield","year":"1997"},{"key":"2023020112014860700_btv738-B8","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"Hopcroft","year":"1979"},{"key":"2023020112014860700_btv738-B9","first-page":"135","author":"I","year":"2010"},{"key":"2023020112014860700_btv738-B10","doi-asserted-by":"crossref","first-page":"162","DOI":"10.1016\/j.tcs.2012.01.047","article-title":"Palindrome pattern matching","volume":"483","author":"I","year":"2013","journal-title":"Theor. Comput. Sci"},{"key":"2023020112014860700_btv738-B11","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1137\/0206024","article-title":"Fast pattern matching in strings","volume":"6","author":"Knuth","year":"1977","journal-title":"SIAM J. Comput"},{"key":"2023020112014860700_btv738-B12","doi-asserted-by":"crossref","first-page":"5365","DOI":"10.1016\/j.tcs.2009.09.013","article-title":"Searching for gapped palindromes","volume":"410","author":"Kolpakov","year":"2009","journal-title":"Theor. Comput. Sci"},{"key":"2023020112014860700_btv738-B13","doi-asserted-by":"crossref","first-page":"3871","DOI":"10.1093\/nar\/14.9.3871","article-title":"Palindromic sequences are associated with sites of DNA breakage during gene conversion","volume":"14","author":"Krawinkel","year":"1986","journal-title":"Nucleic Acids Res"},{"key":"2023020112014860700_btv738-B14","doi-asserted-by":"crossref","first-page":"R61","DOI":"10.1186\/gb-2007-8-4-r61","article-title":"Evolutionary conservation of sequence and secondary structures in CRISPR repeats","volume":"8","author":"Kunin","year":"2007","journal-title":"Genome Biol"},{"key":"2023020112014860700_btv738-B15","doi-asserted-by":"crossref","first-page":"957","DOI":"10.1038\/nmeth.2649","article-title":"Cas9 as a versatile tool for engineering biology","volume":"10","author":"Mali","year":"2013","journal-title":"Nat. Methods"},{"key":"2023020112014860700_btv738-B16","doi-asserted-by":"crossref","first-page":"346","DOI":"10.1145\/321892.321896","article-title":"A new linear-time \u201con-line\u201d algorithm for finding the smallest initial palindrome of a string","volume":"22","author":"Manacher","year":"1975","journal-title":"J. ACM"},{"key":"2023020112014860700_btv738-B17","doi-asserted-by":"crossref","first-page":"1733","DOI":"10.1093\/bioinformatics\/btg268","article-title":"STRING: finding tandem repeats in DNA sequences","volume":"19","author":"Parisi","year":"2003","journal-title":"Bioinformatics"},{"key":"2023020112014860700_btv738-B18","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1093\/bioinformatics\/btn630","article-title":"Sequence progressive alignment, a framework for practical large-scale probabilistic consistency alignment","volume":"25","author":"Paten","year":"2009","journal-title":"Bioinformatics"},{"key":"2023020112014860700_btv738-B19","doi-asserted-by":"crossref","first-page":"1530","DOI":"10.1093\/bioinformatics\/btn223","article-title":"PatMaN: rapid alignment of short sequences to large databases","volume":"24","author":"Pr\u00fcfer","year":"2008","journal-title":"Bioinformatics"},{"key":"2023020112014860700_btv738-B20","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1093\/bioinformatics\/14.1.55","article-title":"Combinatorial pattern discovery in biological sequences: the TEIRESIAS algorithm","volume":"14","author":"Rigoutsos","year":"1998","journal-title":"Bioinformatics"},{"key":"2023020112014860700_btv738-B21","volume-title":"Theory of Computation","author":"Wood","year":"1986"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/32\/8\/1151\/49018836\/bioinformatics_32_8_1151.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/32\/8\/1151\/49018836\/bioinformatics_32_8_1151.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,1]],"date-time":"2023-02-01T22:26:11Z","timestamp":1675290371000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/32\/8\/1151\/1744595"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,12,16]]},"references-count":21,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2016,4,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btv738","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2016,4,15]]},"published":{"date-parts":[[2015,12,16]]}}}