String matching with variable length gaps

Publication: Research - peer-reviewJournal article – Annual report year: 2012

Standard

String matching with variable length gaps. / Bille, Philip; Gørtz, Inge Li; Vildhøj, Hjalte Wedel; Wind, David Kofoed.

In: Theoretical Computer Science, Vol. 443, 2012, p. 25-34.

Publication: Research - peer-reviewJournal article – Annual report year: 2012

Harvard

APA

CBE

MLA

Vancouver

Author

Bille, Philip; Gørtz, Inge Li; Vildhøj, Hjalte Wedel; Wind, David Kofoed / String matching with variable length gaps.

In: Theoretical Computer Science, Vol. 443, 2012, p. 25-34.

Publication: Research - peer-reviewJournal article – Annual report year: 2012

Bibtex

@article{c68e948fd87448eb9deee6d1bc81f5e2,
title = "String matching with variable length gaps",
keywords = "String matching, Variable length gaps, Algorithms",
publisher = "Elsevier BV",
author = "Philip Bille and Gørtz, {Inge Li} and Vildhøj, {Hjalte Wedel} and Wind, {David Kofoed}",
year = "2012",
doi = "10.1016/j.tcs.2012.03.029",
volume = "443",
pages = "25--34",
journal = "Theoretical Computer Science",
issn = "0304-3975",

}

RIS

TY - JOUR

T1 - String matching with variable length gaps

A1 - Bille,Philip

A1 - Gørtz,Inge Li

A1 - Vildhøj,Hjalte Wedel

A1 - Wind,David Kofoed

AU - Bille,Philip

AU - Gørtz,Inge Li

AU - Vildhøj,Hjalte Wedel

AU - Wind,David Kofoed

PB - Elsevier BV

PY - 2012

Y1 - 2012

N2 - We consider string matching with variable length gaps. Given a string T and a pattern P consisting of strings separated by variable length gaps (arbitrary strings of length in a specified range), the problem is to find all ending positions of substrings in T that match P. This problem is a basic primitive in computational biology applications. Let m and n be the lengths of P and T, respectively, and let k be the number of strings in P. We present a new algorithm achieving time O(nlogk+m+α) and space O(m+A), where A is the sum of the lower bounds of the lengths of the gaps in P and α is the total number of occurrences of the strings in P within T. Compared to the previous results this bound essentially achieves the best known time and space complexities simultaneously. Consequently, our algorithm obtains the best known bounds for almost all combinations of m, n, k, A, and α. Our algorithm is surprisingly simple and straightforward to implement. We also present algorithms for finding and encoding the positions of all strings in P for every match of the pattern.

AB - We consider string matching with variable length gaps. Given a string T and a pattern P consisting of strings separated by variable length gaps (arbitrary strings of length in a specified range), the problem is to find all ending positions of substrings in T that match P. This problem is a basic primitive in computational biology applications. Let m and n be the lengths of P and T, respectively, and let k be the number of strings in P. We present a new algorithm achieving time O(nlogk+m+α) and space O(m+A), where A is the sum of the lower bounds of the lengths of the gaps in P and α is the total number of occurrences of the strings in P within T. Compared to the previous results this bound essentially achieves the best known time and space complexities simultaneously. Consequently, our algorithm obtains the best known bounds for almost all combinations of m, n, k, A, and α. Our algorithm is surprisingly simple and straightforward to implement. We also present algorithms for finding and encoding the positions of all strings in P for every match of the pattern.

KW - String matching

KW - Variable length gaps

KW - Algorithms

U2 - 10.1016/j.tcs.2012.03.029

DO - 10.1016/j.tcs.2012.03.029

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

VL - 443

SP - 25

EP - 34

ER -