Algorithms for subsequence combinatorics

Autor: Hui Wang, Cees H. Elzinga, Sven Rahmann
Přispěvatelé: Methods and Techniques, Theoretical Physics, Theoretical Chemistry, Social Inequality and the Life Course (SILC)
Jazyk: angličtina
Rok vydání: 2008
Předmět:
Zdroj: Theoretical Computer Science, 409(3), 394-404. Elsevier
Elzinga, C H, Rahmann, S & Wang, H 2008, ' Algorithms for subsequence combinatorics ', Theoretical Computer Science, vol. 409, no. 3, pp. 394-404 . https://doi.org/10.1016/j.tcs.2008.08.035
ISSN: 0304-3975
DOI: 10.1016/j.tcs.2008.08.035
Popis: A subsequence is obtained from a string by deleting any number of characters; thus in contrast to a substring, a subsequence is not necessarily a contiguous part of the string. Counting subsequences under various constraints has become relevant to biological sequence analysis, to machine learning, to coding theory, to the analysis of categorical time series in the social sciences, and to the theory of word complexity. We present theorems that lead to efficient dynamic programming algorithms to count (1) distinct subsequences in a string, (2) distinct common subsequences of two strings, (3) matching joint embeddings in two strings, (4) distinct subsequences with a given minimum span, and (5) sequences generated by a string allowing characters to come in runs of a length that is bounded from above. © 2008 Elsevier B.V. All rights reserved.
Databáze: OpenAIRE
Externí odkaz: