Alignment free sequence similarity with bounded hamming distance (Contributo in atti di convegno)

Type
Label
  • Alignment free sequence similarity with bounded hamming distance (Contributo in atti di convegno) (literal)
Anno
  • 2014-01-01T00:00:00+01:00 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#doi
  • 10.1109/DCC.2014.57 (literal)
Alternative label
  • Apostolico A.; Guerra C.; Pizzi C. (2014)
    Alignment free sequence similarity with bounded hamming distance
    in Compression Conference (DCC)
    (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori
  • Apostolico A.; Guerra C.; Pizzi C. (literal)
Pagina inizio
  • 183 (literal)
Pagina fine
  • 192 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#url
  • http://www.scopus.com/inward/record.url?eid=2-s2.0-84903466780&partnerID=q2rCbXpz (literal)
Rivista
Note
  • Scopu (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#affiliazioni
  • College of Computing, Georgia Institute of Technology, 801 Atlantic Drive, Atlanta, GA 30318, United States; Istituto di Analisi Dei Sistemi e Informatica, Consiglio Nazionale Delle Ricerche, Rome, Italy; Dipartimento di Ingegneria Dell'Informazione, Università di Padova, Italy (literal)
Titolo
  • Alignment free sequence similarity with bounded hamming distance (literal)
Abstract
  • A growing number of measures of sequence similarity is being based on some underlying notion of relative compressibility. Within this paradigm, similar sequences are expected to share a large number of common substrings, or subsequences, or more complex patterns or motifs, and so on. The computational complexity of such measures varies, and it increases with the complexion of the patterns taken into account. At the low end of the spectrum, most measures based on the bags of shared substrings are typically afforded in linear time. This performance is no longer achievable as soon as some degree of distortion is accepted. In this paper, measures of sequence similarity are introduced and studied in which patterns in a pair are considered similar if they coincide up to a preset number of mismatches, that is, within a bounded Hamming distance. It is shown here that for some such measures bounds are achievable that are slightly better than O(n2). Preliminary experiments demonstrate the potential applicability to phylogeny and classification of similarity measures that are rougher than previously adopted ones. © 2014 IEEE. (literal)
Prodotto di
Autore CNR
Insieme di parole chiave

Incoming links:


Prodotto
Autore CNR di
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#rivistaDi
Insieme di parole chiave di
data.CNR.it