The combinatorial explosion of motif patterns occurring in 1D and 2D arrays leads to the consideration of special classes of motifs growing linearly with the size of the input array. Such motifs, called irredundant motifs, are able to succinctly represent all of the other motifs occurring in the same array within reasonable time and space bounds. In previous work irredundant motifs were extracted from 2D arrays in O (N 2 log 2 n log log n) and O (N 3) time, where N is the size of the 2D input array and n is its largest dimension. In this paper, we present an algorithm to extract irredundant motifs from 2D arrays that is quadratic in the size of the input. The input is defined on a binary alphabet. It is shown that the algorithm is optimal and practically faster than the previous ones. © 2009 Elsevier B.V. All rights reserved.

Rombo, S.E. (2009). Optimal extraction of motif patterns in 2D. INFORMATION PROCESSING LETTERS, 109(17), 1015-1020 [http://www.sciencedirect.com/science/article/pii/S0020019009001926].

Optimal extraction of motif patterns in 2D

ROMBO, Simona Ester
2009-01-01

Abstract

The combinatorial explosion of motif patterns occurring in 1D and 2D arrays leads to the consideration of special classes of motifs growing linearly with the size of the input array. Such motifs, called irredundant motifs, are able to succinctly represent all of the other motifs occurring in the same array within reasonable time and space bounds. In previous work irredundant motifs were extracted from 2D arrays in O (N 2 log 2 n log log n) and O (N 3) time, where N is the size of the 2D input array and n is its largest dimension. In this paper, we present an algorithm to extract irredundant motifs from 2D arrays that is quadratic in the size of the input. The input is defined on a binary alphabet. It is shown that the algorithm is optimal and practically faster than the previous ones. © 2009 Elsevier B.V. All rights reserved.
Rombo, S.E. (2009). Optimal extraction of motif patterns in 2D. INFORMATION PROCESSING LETTERS, 109(17), 1015-1020 [http://www.sciencedirect.com/science/article/pii/S0020019009001926].
File in questo prodotto:
File Dimensione Formato  
ipl09.pdf

Solo gestori archvio

Dimensione 332.75 kB
Formato Adobe PDF
332.75 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

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/10447/64850
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? 6
social impact