Clustering objects into classes such that elements within one group
share common traits is a long-standing challenge, not just in
computational biology. However, in bioinformatics clustering
algorithms play an important role for typical data analysis tasks, for
instance, remote protein homology detection. In the talk, I will
introduce Transitivity Clustering, an approach based on the NP-hard
weighted transitive graph projection problem. It ensures that, given a
pairwise similarity function and a threshold, the average similarity
of objects from the same cluster is above the threshold and the
average similarity between objects from different clusters is below
the threshold. We tackle this hard problem with heuristics and exact
fixed parameter approaches.