In this paper we present an algorithm for the problem of planted structured motif extraction from a set of sequences. This problem is strictly related to the structured motif extraction problem, which has many important applications in molecular biology. We propose an algorithm that uses a simple two-stage approach: first it extracts simple motifs, then the simple motifs are combined in order to extract structured motifs. We compare our algorithm with existing algorithms whose code is available, and which are based on more complex approaches. Our experiments show that, even if in general the problem is NP-hard, our algorithm is able to handle complex instances of the problem in a reasonable amount of time.

An Efficient Algorithm for Planted Composit Motif Extraction / Federico, M.; Valente, Paolo; Leoncini, Mauro; Montangero, Manuela; Cavicchioli, R.. - STAMPA. - (2009), pp. 1-6. (Intervento presentato al convegno 1st Workshop on Breaking Frontiers of Computational Biology, CompBio 2009 tenutosi a ita nel 18 - 20 Maggio 2009) [10.1145/1531780.1531782].

An Efficient Algorithm for Planted Composit Motif Extraction

VALENTE, Paolo;LEONCINI, Mauro;MONTANGERO, Manuela;R. Cavicchioli
2009

Abstract

In this paper we present an algorithm for the problem of planted structured motif extraction from a set of sequences. This problem is strictly related to the structured motif extraction problem, which has many important applications in molecular biology. We propose an algorithm that uses a simple two-stage approach: first it extracts simple motifs, then the simple motifs are combined in order to extract structured motifs. We compare our algorithm with existing algorithms whose code is available, and which are based on more complex approaches. Our experiments show that, even if in general the problem is NP-hard, our algorithm is able to handle complex instances of the problem in a reasonable amount of time.
2009
1st Workshop on Breaking Frontiers of Computational Biology, CompBio 2009
ita
18 - 20 Maggio 2009
1
6
Federico, M.; Valente, Paolo; Leoncini, Mauro; Montangero, Manuela; Cavicchioli, R.
An Efficient Algorithm for Planted Composit Motif Extraction / Federico, M.; Valente, Paolo; Leoncini, Mauro; Montangero, Manuela; Cavicchioli, R.. - STAMPA. - (2009), pp. 1-6. (Intervento presentato al convegno 1st Workshop on Breaking Frontiers of Computational Biology, CompBio 2009 tenutosi a ita nel 18 - 20 Maggio 2009) [10.1145/1531780.1531782].
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

Licenza Creative Commons
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

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