title: MADMX: a strategy for maximal dense motif extraction.
abstract: We develop, analyze, and experiment with a new tool, called MADMX, which extracts frequent motifs from biological sequences. We introduce the notion of density to single out the "significant" motifs. The density is a simple and flexible measure for bounding the number of don't cares in a motif, defined as the fraction of solid (i.e., different from don't care) characters in the motif. A maximal dense motif has density above a certain threshold, and any further specialization of a don't care symbol in it or any extension of its boundaries decreases its number of occurrences in the input sequence. By extracting only maximal dense motifs, MADMX reduces the output size and improves performance, while enhancing the quality of the discoveries. The efficiency of our approach relies on a newly defined combining operation, dubbed fusion, which allows for the construction of maximal dense motifs in a bottom-up fashion, while avoiding the generation of nonmaximal ones. We provide experimental evidence of the efficiency and the quality of the motifs returned by MADMX.
authors.affiliation: Dipartimento di Informatica, Università di Pisa, Italy.
authors.forename: Roberto
authors.initials: R
authors.lastname: Grossi
authors.forename: Andrea
authors.initials: A
authors.lastname: Pietracaprina
authors.forename: Nadia
authors.initials: N
authors.lastname: Pisanti
authors.forename: Geppino
authors.initials: G
authors.lastname: Pucci
authors.forename: Eli
authors.initials: E
authors.lastname: Upfal
authors.forename: Fabio
authors.initials: F
authors.lastname: Vandin
mesh_terms: D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D017421:Sequence Analysis / Q000379:methods*