Efficient Pattern Matching in Elastic-Degenerate Texts

详细信息    查看全文

• 关键词：String processing algorithms ; Degenerate strings ; Indeterminate strings ; Elastic ; degenerate strings ; Gapped strings
• 刊名：Lecture Notes in Computer Science
• 出版年：2017
• 出版时间：2017
• 年：2017
• 卷：10168
• 期：1
• 页码：131-142
• 丛书名：Language and Automata Theory and Applications
• ISBN：978-3-319-53733-7
• 卷排序：10168

文摘

Motivated by applications in bioinformatics, in what follows, we extend the notion of gapped strings to elastic-degenerate strings. An elastic-degenerate string can been seen as an ordered collection of solid (standard) strings interleaved by elastic-degenerate symbols; each such symbol corresponds to a set of two or more variable-length solid strings. In this article, we present an algorithm for solving the pattern matching problem with a solid pattern and an elastic-degenerate text running in \(\mathcal {O}(N+\alpha \gamma mn)\) time; where m is the length of the pattern; n and N are the length and total size of the elastic-degenerate text, respectively; \(\alpha \) and \(\gamma \) are parameters, respectively representing the maximum number of strings in any elastic-degenerate symbol of the text and the maximum number of elastic-degenerate symbols spanned by any occurrence of the pattern in the text. The space used by the proposed algorithm is \(\mathcal {O}(N)\).