Skip to main content

Motif discovery from 2D arrays and applications

Simona Rombo ( Universit√° degli Studi di Palermo, Italy )

The analysis of digital images often involves the search of rectangular boxes that are frequently repeated in one or several input images. Digital images may be modeled by 2D arrays, from which motif patterns consisting of sequences of intermixed solid and don’t-care characters are extracted. In order to alleviate the exponential growth of such motifs, notions of maximal saturation and irredundancy have been formulated, whereby more or less compact subsets of the set of all motifs can be extracted, that are capable of expressing all others by suitable combinations. In this talk, the notion of maximal irredundant motifs in two-dimensional arrays will be explained and a combinatorial argument that poses a linear bound on the total number of such motifs will be presented as well. Then different approaches to the discovery of 2D irredundant motifs will be discussed and some applications for digital images compression and classification will be illustrated.

Speaker bio

Simona E. Rombo is an Assistant Professor at the Department of Mathematics and Computer Science of the University of Palermo (Palermo, Italy) since September 2012. She was a Research Fellow at ICAR-CNR (July 2010 / September 2012) and at DEIS of University of Calabria (Cosenza, Italy) since March 2006 to June 2010. Her main research activities focus on combinatorial algorithms for bioinformatics and digital images, with applications in data compression and information retrieval. She was a visiting scientist at the College of Computing of the Georgia Institute of Technology, where she worked on motif extraction and data compression, and at the Computer Science Department of the Purdue University (West Lafayette, Indiana, USA), where she started her studies on motif extraction from digital images. She got both her doctoral degree in Computer Sciences, Biomedicine and Telecommunications and her laurea degree in Electronic Engineering from the University "Mediterranea" of Reggio Calabria (Reggio Calabria, Italy).

Share this: