bbq

Discovering cis-regulatory modules (clusters of transcription factor binding sites)

Axel Mosig, 2005.

bbq is a command-line tool for discovering clusters of transcription factor binding sites that occur simultaneously in several genome sequences. Finding such clusters – which are sometimes also referred to as cis-regulatory modules – is done in a multiple-alignment-like fashion by solving a certain combinatorial and geometric optimization problem, the so-called best barbeque problem (explaining the name bbq). As opposed to classical, typically dynamic programming based, alignment procedures, the order of the binding sites' occurences can be arbitrarily shuffled, so that bbq is the result of developing completely new algorithms.

The implementation provided here supports numerous features such as weighted sets, p-value based weighting schemes or computing the best h solutions instead of only the best solution. Most of these features are supported by two algorithms representing two different approaches to solving the given optimization problem. Output can be visualized in postscript.