Motif matching using gapped patterns

DOI10.1016/J.TCS.2014.06.032MaRDI QIDQ401471zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Emanuele Giaquinta, Kimmo Fredriksson, Szymon Grabowski, Alexandru I. Tomescu, Esko Ukkonen

Publication date 27 August 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1306.2483

zbMATH Keywords

combinatorial problemsstring algorithmsmultiple pattern matchingpattern matching with gapsword-level parallelism

Mathematics Subject Classification ID

Combinatorics on words (68R15) Algorithms on strings (68W32)

Abstract: We present new algorithms for the problem of multiple string matching of gapped patterns, where a gapped pattern is a sequence of strings such that there is a gap of fixed length between each two consecutive strings. The problem has applications in the discovery of transcription factor binding sites in DNA sequences when using generalized versions of the Position Weight Matrix model to describe transcription factor specificities. In these models a motif can be matched as a set of gapped patterns with unit-length keywords. The existing algorithms for matching a set of gapped patterns are worst-case efficient but not practical, or vice versa, in this particular case. The novel algorithms that we present are based on dynamic programming and bit-parallelism, and lie in a middle-ground among the existing algorithms. In fact, their time complexity is close to the best existing bound and, yet, they are also practical. We also provide experimental results which show that the presented algorithms are fast in practice, and preferable if all the strings in the patterns have unit-length.

Recommendations

• Motif matching using gapped patterns
• On the complexity of finding gapped motifs
• Structural Analysis of Gapped Motifs of a String
• A FIRST APPROACH TO FINDING COMMON MOTIFS WITH GAPS
• Large Scale Matching for Position Weight Matrices

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Constructing Efficient Dictionaries in Close to Sorting Time
• Efficient Bit-Parallel Algorithms for (δ,α)-Matching
• Efficient string matching
• Fast profile matching algorithms - A survey
• Finding Patterns with Variable Length Gaps or Don’t Cares
• Nested Counters in Bit-Parallel String Matching
• New techniques for regular expression searching
• Online matching of multiple regular patterns with gaps and character classes
• Regular expression matching with multi-strings and intervals
• String matching with variable length gaps

Cited in

(12)

• scientific article; zbMATH DE number 1615291 (Why is no real title available?)
• Structural Analysis of Gapped Motifs of a String
• Missing pattern discovery
• Simple algorithm for pattern-matching with bounded gaps in genomic sequences
• On the complexity of finding gapped motifs
• scientific article; zbMATH DE number 2087049 (Why is no real title available?)
• Finding Common Motifs with Gaps Using Finite Automata
• Large Scale Matching for Position Weight Matrices
• String matching with variable length gaps
• Motif matching using gapped patterns
• An efficient algorithm for attribute-based subsequence matching
• A FIRST APPROACH TO FINDING COMMON MOTIFS WITH GAPS

This page was built for publication: Motif matching using gapped patterns

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q401471)