@inbook{497304ef87d04e9b95914cfcfd6d5265,
title = "Finding optimal pairs of cooperative and competing patterns with bounded distance",
abstract = "We consider the problem of discovering the optimal pair of substring patterns with bounded distance α, from a given set S of strings. We study two kinds of pattern classes, one is in form p ∧α q that are interpreted as cooperative patterns within α distance, and the other is in form p ∧α ¬q representing competing patterns, with respect to S. We show an efficient algorithm to find the optimal pair of patterns in O(N2) time using O(N) space. We also present an O(m 2N2) time and O(m2N) space solution to a more difficult version of the optimal pattern pair discovery problem, where m denotes the number of strings in S.",
author = "Shunsuke Inenaga and Hideo Bannai and Heikki Hyyr{\"o} and Ayumi Shinohara and Masayuki Takeda and Kenta Nakai and Satoru Miyano",
year = "2004",
doi = "10.1007/978-3-540-30214-8_3",
language = "English",
isbn = "9783540233572",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "32--46",
editor = "Einoshin Suzuki and Setsuo Arikawa",
booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
address = "Germany",
}