Go to the content. | Move to the navigation | Go to the site search | Go to the menu | Contacts | Accessibility

| Create Account

Apostolico, Alberto and Comin, Matteo and Parida, Laxmin (2006) Mining, compressing and classifying with extensible motifs. [Online journal papers]

Full text disponibile come:

Documento PDF

Per gentile concessione di: http://www.almob.org/content/1/1/4

Abstract (english)


Motif patterns of maximal saturation emerged originally in contexts of pattern discovery in biomolecular sequences and have recently proven a valuable notion also in the design of data compression schemes. Informally, a motif is a string of intermittently solid and wild characters that recurs more or less frequently in an input sequence or family of sequences. Motif discovery techniques and tools tend to be computationally imposing, however, special classes of "rigid" motifs have been identified of which the discovery is affordable in low polynomial time.


In the present work, "extensible" motifs are considered such that each sequence of gaps comes endowed with some elasticity, whereby the same pattern may be stretched to fit segments of the source that match all the solid characters but are otherwise of different lengths. A few applications of this notion are then described. In applications of data compression by textual substitution, extensible motifs are seen to bring savings on the size of the codebook, and hence to improve compression. In germane contexts, in which compressibility is used in its dual role as a basis for structural inference and classification, extensible motifs are seen to support unsupervised classification and phylogeny reconstruction.


Off-line compression based on extensible motifs can be used advantageously to compress and classify biological sequences.

Statistiche Download - Aggiungi a RefWorks
EPrint type:Online journal papers
Anno di Pubblicazione:2006
Key Words:motifs, biomolecular sequences
Settori scientifico-disciplinari MIUR:Area 05 - Scienze biologiche > BIO/13 Biologia applicata
Area 01 - Scienze matematiche e informatiche > INF/01 Informatica
Struttura di riferimento:Dipartimenti > Dipartimento di Ingegneria dell'Informazione
Codice ID:1211
Depositato il:09 Dec 2008
Simple Metadata
Full Metadata
EndNote Format

Download statistics

Solo per lo Staff dell Archivio: Modifica questo record