A Comparative Study of Bases for Motif Inference - Archive ouverte HAL Accéder directement au contenu
Communication Dans Un Congrès Année : 2005

A Comparative Study of Bases for Motif Inference

Marie-France Sagot

Résumé

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.
Fichier principal
Vignette du fichier
nato.pdf (280.71 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00620115 , version 1 (26-03-2013)

Identifiants

  • HAL Id : hal-00620115 , version 1

Citer

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⟩
319 Consultations
96 Téléchargements

Partager

Gmail Facebook X LinkedIn More