The aim of the motif recognition problem is to detect a set of mutually similar subsequences within a collection of biological sequences. The weak motif recognition problem on DNA sequences is where the sequences are highly degenerate. Our new approach to this problem uses a weighted graph model and a heuristic that determines high weight subgraphs in polynomial time. Our experimental tests show impressive accuracy and efficiency. We also give results that demonstrate a theoretical dichotomy between cliques in our graph that represent actual motifs and those that do not.

Christina Boucher, Daniel Brown and Paul Church.A graph-clustering approach to weak motif recognition. In proceedings of the 7th Workshop on Algorithms in Bioinformatics (WABI 2007), pages 149--160.