Finding optimal pairs of cooperative and competing patterns with bounded distance

Shunsuke Inenaga; Hideo Bannai; Heikki Hyyrö; Ayumi Shinohara; Masayuki Takeda; Kenta Nakai; Satoru Miyano

doi:10.1007/978-3-540-30214-8_3

Finding optimal pairs of cooperative and competing patterns with bounded distance

Shunsuke Inenaga, Hideo Bannai, Heikki Hyyrö, Ayumi Shinohara, Masayuki Takeda, Kenta Nakai, Satoru Miyano

Mathematical Informatics

Research output: Chapter in Book/Report/Conference proceeding › Chapter

11 Citations (Scopus)

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(N²) time using O(N) space. We also present an O(m ²N²) time and O(m²N) space solution to a more difficult version of the optimal pattern pair discovery problem, where m denotes the number of strings in S.

Original language	English
Title of host publication	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Editors	Einoshin Suzuki, Setsuo Arikawa
Publisher	Springer Verlag
Pages	32-46
Number of pages	15
ISBN (Print)	9783540233572
DOIs	https://doi.org/10.1007/978-3-540-30214-8_3
Publication status	Published - 2004

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	3245
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-540-30214-8_3

Cite this

Inenaga, S., Bannai, H., Hyyrö, H., Shinohara, A., Takeda, M., Nakai, K., & Miyano, S. (2004). Finding optimal pairs of cooperative and competing patterns with bounded distance. In E. Suzuki, & S. Arikawa (Eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 32-46). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3245). Springer Verlag. https://doi.org/10.1007/978-3-540-30214-8_3

Finding optimal pairs of cooperative and competing patterns with bounded distance. / Inenaga, Shunsuke; Bannai, Hideo; Hyyrö, Heikki et al.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). ed. / Einoshin Suzuki; Setsuo Arikawa. Springer Verlag, 2004. p. 32-46 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3245).

Research output: Chapter in Book/Report/Conference proceeding › Chapter

Inenaga, S, Bannai, H, Hyyrö, H, Shinohara, A, Takeda, M, Nakai, K & Miyano, S 2004, Finding optimal pairs of cooperative and competing patterns with bounded distance. in E Suzuki & S Arikawa (eds), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 3245, Springer Verlag, pp. 32-46. https://doi.org/10.1007/978-3-540-30214-8_3

Inenaga S, Bannai H, Hyyrö H, Shinohara A, Takeda M, Nakai K et al. Finding optimal pairs of cooperative and competing patterns with bounded distance. In Suzuki E, Arikawa S, editors, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer Verlag. 2004. p. 32-46. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-30214-8_3

Inenaga, Shunsuke ; Bannai, Hideo ; Hyyrö, Heikki et al. / Finding optimal pairs of cooperative and competing patterns with bounded distance. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). editor / Einoshin Suzuki ; Setsuo Arikawa. Springer Verlag, 2004. pp. 32-46 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@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",

}

TY - CHAP

T1 - Finding optimal pairs of cooperative and competing patterns with bounded distance

AU - Inenaga, Shunsuke

AU - Bannai, Hideo

AU - Hyyrö, Heikki

AU - Shinohara, Ayumi

AU - Takeda, Masayuki

AU - Nakai, Kenta

AU - Miyano, Satoru

PY - 2004

Y1 - 2004

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=35048874277&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=35048874277&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-30214-8_3

DO - 10.1007/978-3-540-30214-8_3

M3 - Chapter

AN - SCOPUS:35048874277

SN - 9783540233572

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 32

EP - 46

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

A2 - Suzuki, Einoshin

A2 - Arikawa, Setsuo

PB - Springer Verlag

ER -

Finding optimal pairs of cooperative and competing patterns with bounded distance

Abstract

Publication series

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this