TreeCluster

TreeCluster performs phylogenetic clustering of biological sequences by partitioning a phylogenetic tree to produce clusters that satisfy distance and branch-support constraints.

Key Features:

• Phylogenetic tree input: Accepts a phylogenetic tree in Newick format and leverages evolutionary relationships among sequences for clustering.
• Distance and support thresholds: Allows specification of a distance threshold t and an optional branch-support threshold s, ensuring no pair of leaves within any cluster is connected by branches with support less than or equal to s.
• Optimization objectives: Solves three specific optimization problems: limiting the diameter of each cluster, constraining the sum of branch lengths within a cluster, and managing chains of pairwise distances between sequences in a cluster.
• Minimization goal: Minimizes the number of clusters while adhering to user-defined heterogeneity constraints.
• Efficiency: Implements algorithms whose time complexity scales linearly with the size of the tree.
• Singleton designation: Permits designating leaves as singletons (cluster = -1) when they do not cluster with other sequences.

Scientific Applications:

• OTU clustering for microbiome data: Clusters operational taxonomic units (OTUs) using phylogenetic relationships for microbiome dataset analysis.
• HIV transmission clustering: Groups HIV sequences by phylogenetic relatedness to support analyses of transmission dynamics.
• Divide-and-conquer multiple sequence alignment: Partitions sequences for divide-and-conquer multiple sequence alignment workflows.

Methodology:

Implements algorithms from theoretical computer science that use tree-based distances to minimize the number of clusters under a user-specified distance threshold t and optional branch-support threshold s, with linear time complexity in the size of the tree.