http://www.cnr.it/ontology/cnr/individuo/prodotto/ID64093

-based classification of biological sequences and structures via the Universal Similarity Metric: experimental assessment (Articolo in rivista)

Type

Prodotto della ricerca (Classe)
Articolo in rivista (Classe)

Label

-based classification of biological sequences and structures via the Universal Similarity Metric: experimental assessment (Articolo in rivista) (literal)

Anno

2007-01-01T00:00:00+01:00 (literal)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#doi

10.1186/1471-2105-8-252 (literal)

Alternative label

[1] Manzini G., [2] Ferragina P., [3] Giancarlo R., [3] Greco V., [4] Valiente G. (2007)
-based classification of biological sequences and structures via the Universal Similarity Metric: experimental assessment
in BMC bioinformatics; Biomed Central Ltd., London (Regno Unito)
(literal)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori

[1] Manzini G., [2] Ferragina P., [3] Giancarlo R., [3] Greco V., [4] Valiente G. (literal)

Pagina inizio

252 (literal)

Pagina fine

272 (literal)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#numeroVolume

8 (literal)

Rivista

BMC bioinformatics (Rivista)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#note

DOI: http://dx.doi.org/10.1186/1471-2105-8-252 (literal)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#pagineTotali

21 (literal)

Note

Scopu (literal)
ISI Web of Science (WOS) (literal)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#affiliazioni

[1] CNR-IIT, Pisa, Italy; [2] Dipartimento di Informatica, Università di Pisa, Italy; [3] Dipartimento di Matematica Applicazioni, Università di Palermo, Italy; [4] Algorithms, Bioinformatics, Complexity and Formal Methods Research Group, Technical University of Catalonia, Spain (literal)

Titolo

-based classification of biological sequences and structures via the Universal Similarity Metric: experimental assessment (literal)

Abstract

Similarity of sequences is a key mathematical notion for Classification and Phylogenetic studies in Biology. It is currently primarily handled using alignments. However, the alignment methods seem inadequate for post-genomic studies since they do not scale well with data set size and they seem to be confined only to genomic and proteomic sequences. Therefore, alignment-free similarity measures are actively pursued. Among those, USM (Universal Similarity Metric) has gained prominence. It is based on the deep theory of Kolmogorov Complexity and universality is its most novel striking feature. Since it can only be approximated via data compression, USM is a methodology rather than a formula quantifying the similarity of two strings. Three approximations of USM are available, namely UCD (Universal Compression Dissimilarity), NCD (Normalized Compression Dissimilarity) and CD (Compression Dissimilarity). We experimentally test the USM methodology by using 25 compressors, all three of its known approximations and six data sets of relevance to Molecular Biology. This offers the first systematic and quantitative experimental assessment of this methodology, that naturally complements the many theoretical and the preliminary experimental results available. Moreover, we compare the USM methodology both with methods based on alignments and not. We may group our experiments into two sets. The first one, performed via ROC (Receiver Operating Curve) analysis, aims at assessing the intrinsic ability of the methodology to discriminate and classify biological sequences and structures. A second set of experiments aims at assessing how well two commonly available classification algorithms, UPGMA (Unweighted Pair Group Method with Arithmetic Mean) and NJ (Neighbor Joining), can use the methodology to perform their task, their performance being evaluated against gold standards and with the use of well known statistical indexes, i.e., the F-measure and the partition distance. (literal)

Editore