Phylogibbs

PhyloGibbs is a software tool that solves one of the most pressing challenges in bioinformatics - identifying binding sites for regulatory proteins. The tool leverages comparative analysis of orthologous intergenic regions of related species to identify short and fuzzy sequence patterns indicative of functional sites. To achieve this, PhyloGibbs uses a sophisticated motif sampling algorithm that searches for binding sites in multiple sequence alignments of orthologous sequences.

The algorithm scores various binding site configurations using a Bayesian probabilistic model that treats aligned sequences by a model for the evolution of binding sites and "background" intergenic DNA. This model considers the phylogenetic relationship between the species in the alignment explicitly, which is critical to distinguish conservation due to the occurrence of functional sites from spurious conservation due to evolutionary proximity. Additionally, the algorithm uses simulated annealing and Monte Carlo Markov-chain sampling to assign posterior probabilities to all the binding sites it reports.

PhyloGibbs has been rigorously tested on synthetic and real data from five Saccharomyces species. The results demonstrate that it performs significantly better than four other motif-finding algorithms, including algorithms considering phylogeny. Furthermore, PhyloGibbs can make realistic estimates of the reliability of its predictions, which is a significant advantage over other algorithms.