Searching a multivariate partition space using weighted MAX-SAT

Silvia Liverani, James Cussens, Jim Q. Smith

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Because of the huge number of partitions of even a moderately sized dataset, even when Bayes factors have a closed form, a comprehensive search for the highest scoring (MAP) partition is usually impossible. Therefore, both deterministic or random search algorithms traverse only a small proportion of partitions of a large dataset. The main contribution of this paper is to encode the formal Bayes factor search on partitions as a weighted MAX-SAT problem and use well-known solvers for that problem to search for partitions. We demonstrate how, with the appropriate priors over the partition space, this method can be used to fully search the space of partitions in smaller problems and how it can be used to enhance the performance of more familiar algorithms in large problems. We illustrate our method on clustering of time-course microarray experiments.
Original languageEnglish
Title of host publicationProceedings of the Sixth International Meeting on Computational Intelligence Methods for Bioinformatics and Biostatistics (CIBB) 2009
EditorsF. Masulli, L. Peterson, R. Tagliaferri
Number of pages14
ISBN (Print)978-3-642-14570-4
Publication statusPublished - 2010

Publication series

NameLNBI 6160

Cite this