Searching a multivariate partition space using weighted MAX-SAT

Silvia Liverani, James Cussens, Jim Q. Smith, L. Peterson

Research output: Other 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
Number of pages14
ISBN (Print)978-3-642-14570-4
Publication statusPublished - 2010


Dive into the research topics of 'Searching a multivariate partition space using weighted MAX-SAT'. Together they form a unique fingerprint.

Cite this