Algorithms for subsequence combinatorics

C.H. Elzinga, S. Rahmann, H. Wang

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

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.
Original languageEnglish
Pages (from-to)394-404
Number of pages11
JournalTheoretical Computer Science
Volume409
Issue number3
DOIs
Publication statusPublished - 2008

Fingerprint

Dive into the research topics of 'Algorithms for subsequence combinatorics'. Together they form a unique fingerprint.

Cite this