TY - CHAP
T1 - Finding missing patterns
AU - Inenaga, Shunsuke
AU - Kivioja, Teemu
AU - Mäkinen, Veli
PY - 2004
Y1 - 2004
N2 - Consider the following problem: Find the shortest pattern that does not occur in a given text. To make the problem non-trivial, the pattern is required to consist only of characters that occur in the text. This problem can be solved easily in linear time using the suffix tree of the text. In this paper, we study an extension of this problem, namely the missing patterns problem: Find the shortest pair of patterns that do not occur close to each other in a given text, i.e., the distance between their occurrences is always greater than a given threshold a. We show that the missing patterns problem can be solved in O(min(αn log n, n2)) time, where n is the size of the text. For the special case where both pairs are required to have the same length, we give an algorithm with time complexity O(αn log log n). The problem is motivated by optimization of multiplexed nested-PCR.
AB - Consider the following problem: Find the shortest pattern that does not occur in a given text. To make the problem non-trivial, the pattern is required to consist only of characters that occur in the text. This problem can be solved easily in linear time using the suffix tree of the text. In this paper, we study an extension of this problem, namely the missing patterns problem: Find the shortest pair of patterns that do not occur close to each other in a given text, i.e., the distance between their occurrences is always greater than a given threshold a. We show that the missing patterns problem can be solved in O(min(αn log n, n2)) time, where n is the size of the text. For the special case where both pairs are required to have the same length, we give an algorithm with time complexity O(αn log log n). The problem is motivated by optimization of multiplexed nested-PCR.
UR - http://www.scopus.com/inward/record.url?scp=33646730028&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33646730028&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-30219-3_39
DO - 10.1007/978-3-540-30219-3_39
M3 - Chapter
AN - SCOPUS:33646730028
SN - 3540230181
SN - 9783540230182
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 463
EP - 474
BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
A2 - Jonassen, Inge
A2 - Kim, Junhyong
PB - Springer Verlag
ER -