Missing pattern discovery

Stanislav Angelov; Shunsuke Inenaga; Teemu Kivioja; Veli Mäkinen

doi:10.1016/j.jda.2010.08.005

Missing pattern discovery

Stanislav Angelov, Shunsuke Inenaga, Teemu Kivioja, Veli Mäkinen

Mathematical Informatics

Research output: Contribution to journal › Article › peer-review

Abstract

In this paper, we study 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 α. We present various solutions to this problem, as well as to the case where the patterns in the pair are required to be of the same length. This work is motivated by optimizing the sensitivity of PCR. Experiments show that our algorithm is practical enough to handle human genome data.

Original language	English
Pages (from-to)	153-165
Number of pages	13
Journal	Journal of Discrete Algorithms
Volume	9
Issue number	2
DOIs	https://doi.org/10.1016/j.jda.2010.08.005
Publication status	Published - Jun 2011

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1016/j.jda.2010.08.005

Cite this

@article{291b43056f38446e9b017eb186acde2e,

title = "Missing pattern discovery",

abstract = "In this paper, we study 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 α. We present various solutions to this problem, as well as to the case where the patterns in the pair are required to be of the same length. This work is motivated by optimizing the sensitivity of PCR. Experiments show that our algorithm is practical enough to handle human genome data.",

author = "Stanislav Angelov and Shunsuke Inenaga and Teemu Kivioja and Veli M{\"a}kinen",

year = "2011",

month = jun,

doi = "10.1016/j.jda.2010.08.005",

language = "English",

volume = "9",

pages = "153--165",

journal = "Journal of Discrete Algorithms",

issn = "1570-8667",

publisher = "Elsevier",

number = "2",

}

TY - JOUR

T1 - Missing pattern discovery

AU - Angelov, Stanislav

AU - Inenaga, Shunsuke

AU - Kivioja, Teemu

AU - Mäkinen, Veli

PY - 2011/6

Y1 - 2011/6

N2 - In this paper, we study 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 α. We present various solutions to this problem, as well as to the case where the patterns in the pair are required to be of the same length. This work is motivated by optimizing the sensitivity of PCR. Experiments show that our algorithm is practical enough to handle human genome data.

AB - In this paper, we study 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 α. We present various solutions to this problem, as well as to the case where the patterns in the pair are required to be of the same length. This work is motivated by optimizing the sensitivity of PCR. Experiments show that our algorithm is practical enough to handle human genome data.

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

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

U2 - 10.1016/j.jda.2010.08.005

DO - 10.1016/j.jda.2010.08.005

M3 - Article

AN - SCOPUS:79952359450

SN - 1570-8667

VL - 9

SP - 153

EP - 165

JO - Journal of Discrete Algorithms

JF - Journal of Discrete Algorithms

IS - 2

ER -

Missing pattern discovery

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this