  We present a global optimization algorithm for clustering data given the
ratio of likelihoods that each pair of data points is in the same cluster or in
different clusters. To define a clustering solution in terms of pairwise
relationships, a necessary and sufficient condition is that belonging to the
same cluster satisfies transitivity. We define a global objective function
based on pairwise likelihood ratios and a transitivity constraint over all
triples, assigning an equal prior probability to all clustering solutions. We
maximize the objective function by implementing max-sum message passing on the
corresponding factor graph to arrive at an O(N^3) algorithm. Lastly, we
demonstrate an application inspired by mutational sequencing for decoding
random binary words transmitted through a noisy channel.
