TreeCluster: Clustering biological sequences using phylogenetic trees.

Area of Science:

• Bioinformatics
• Computational Biology
• Phylogenetics

Background:

• Sequence clustering is vital in bioinformatics but often relies on pairwise distances, neglecting inherent phylogenetic relationships.
• Phylogenetic trees naturally represent these relationships, yet tree-based clustering remains under-utilized despite advances in phylogenetic inference.

Purpose of the Study:

• To introduce and implement a novel tree-based clustering framework for homologous sequences.
• To define and solve optimization problems for clustering based on tree topology and branch lengths.
• To evaluate the efficacy of tree-based clustering in diverse bioinformatics applications.

Main Methods:

• Defined a family of optimization problems for tree-based clustering with heterogeneity constraints (diameter, branch length sum, pairwise distance chains).
• Developed linear-time algorithms for these tree-clustering problems, leveraging existing theoretical computer science solutions.
• Implemented the algorithms in a software tool named TreeCluster.

Main Results:

• TreeCluster successfully applied to Operational Taxonomic Unit (OTU) clustering in microbiome data, HIV transmission network analysis, and multiple sequence alignment.
• Tree-based clustering generated more internally consistent clusters compared to traditional distance-based methods.
• Downstream applications demonstrated improved effectiveness when utilizing TreeCluster's outputs.

Conclusions:

• Tree-based clustering is a powerful, under-utilized approach for analyzing homologous sequences.
• The TreeCluster tool provides an efficient and effective implementation for various bioinformatics tasks.
• This work advocates for the broader adoption of phylogenetic relationships in sequence clustering methodologies.