A Comparative Study of Bases for Motif Inference

Abstract : Motif inference is at the heart of several time-demanding computational tasks, such as in molecular biology, data mining and identification of structured motifs in sequences, and in data compression, to name a few. In this scenario, a motif is a pattern that appears repeated at least a certain number of times (the quorum), to be of interest. The pattern can be approximated in that some of its characters can be left unspecified (the don't cares). Motif inference is not aimed at searching a given pattern but, rather, at discovering all the possible patterns that appear as motifs in the given input string. The combinatorial explosion of these patterns makes their discover an exponential-time computation. For this, the notion of basis has been recently introduced to succinctly represent all of them within reasonable time and space bounds. The goal of the paper is to shed light on the state of the art for this emerging field and to add further properties to what is currently known.
Document type :
Conference papers
Complete list of metadatas

Cited literature [16 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00620115
Contributor : Maxime Crochemore <>
Submitted on : Tuesday, March 26, 2013 - 12:21:00 AM
Last modification on : Thursday, November 21, 2019 - 1:14:17 PM
Long-term archiving on: Thursday, June 27, 2013 - 2:50:11 AM

File

nato.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00620115, version 1

Citation

Nadia Pisanti, Maxime Crochemore, Roberto Grossi, Marie-France Sagot. A Comparative Study of Bases for Motif Inference. String Algorithmics, 2005, Londres, United Kingdom. pp.195-225. ⟨hal-00620115⟩

Share

Metrics

Record views

541

Files downloads

98