A novel specialized single-linkage clustering algorithm for taxonomically ordered data.

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Ortholog gene similarities are often represented by alignment matrices.
• Single-linkage clustering of gene clusters has a time complexity of O(n × m).

Purpose of the Study:

• To develop computationally efficient methods for gene clustering.
• To improve upon the complexity and quality of existing clustering algorithms.

Main Methods:

• Exploiting species order from phylogenetic tree traversals to reduce alignment matrix scope.
• Introducing novel hierarchical and consecutive clustering algorithms.
• Analyzing time complexity and cluster quality metrics.

Main Results:

• Achieved amortized O(|S|) time for hierarchical clustering and linear O(|S|) for consecutive clustering.
• Demonstrated higher cluster densities and superior cluster quality compared to single-linkage clustering.
• Both novel approaches produce identical clusters, with hierarchical clustering also yielding dendrograms.

Conclusions:

• The proposed methods offer significant computational advantages over single-linkage clustering.
• The novel approaches maintain or enhance cluster quality, leading to more reliable results.
• These methods provide a more efficient and accurate way to cluster ortholog genes.