Motif-Finding Algorithms: The Challenge of Searching for Unknown Patterns

Alessandro Bogliolo, Associate Professor at University of Urbino, Italy

 

Abstract: A motif, in computational biology, is a recurrent pattern that is conjectured to be biologically relevant. Most biological sequence analysis are based on the assumption that relevant patterns are unlikely to be encountered by chance. In other words, a pattern is conjectured to be biologically relevant if it is found a number of times that would be hardly explained by a random model.

According to this assumption, motif finding looks for patterns that have a large number of occurrences in a given set of sequences. Despite the simplicity of its statement, motif finding is a challenging task since the patterns of interest are usually of unknown length and they have approximate occurrences in the given set of sequences. Moreover, in practical cases the pattern of interest may not be statistically relevant, being undistinguishable from random noise.

This talk provides a comparative overview of existing approaches to motif finding, discusses their inherent limitations, presents a new motif-finding algorithm and explores non-biological applications.

Download visuals (pdf 372 KB)