With the progress of modern sequencing technologies a number of complete genomes is now available. Traditional motif discovery tools cannot handle this massive amount of data, therefore the comparison of complete genomes can be carried out only with ad hoc methods. In this work we propose a distance function based on subword compositions, which extends the Average Common Subword approach(ACS) of Ulitsky et al. ACS is closely related to the cross entropy estimated between two entire genome sequences, and thus to some set of ``independent'' subwords, namely their redundant common subwords. Then, we filter their redundant common subwords by means of underlying-paired motifs, which relate to each other regions of two genome sequences. This set of motifs is, by construction, linear in the size of input and without overlap; we call the selected motifs, underlying-paired irredundant common subwords, or simply unic subwords. Preliminary results show the validity of our method, and suggest novel computational approaches for analyzing the evolution of genomes.

Whole-Genome Phylogeny by Virtue of Unic Subwords

COMIN, MATTEO;
2012

Abstract

With the progress of modern sequencing technologies a number of complete genomes is now available. Traditional motif discovery tools cannot handle this massive amount of data, therefore the comparison of complete genomes can be carried out only with ad hoc methods. In this work we propose a distance function based on subword compositions, which extends the Average Common Subword approach(ACS) of Ulitsky et al. ACS is closely related to the cross entropy estimated between two entire genome sequences, and thus to some set of ``independent'' subwords, namely their redundant common subwords. Then, we filter their redundant common subwords by means of underlying-paired motifs, which relate to each other regions of two genome sequences. This set of motifs is, by construction, linear in the size of input and without overlap; we call the selected motifs, underlying-paired irredundant common subwords, or simply unic subwords. Preliminary results show the validity of our method, and suggest novel computational approaches for analyzing the evolution of genomes.
2012
23rd International Workshop on Database and Expert Systems Applications
9780769548012
9781467326216
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11577/2533091
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 17
  • ???jsp.display-item.citation.isi??? 13
social impact