Fast Optimal Circular Clustering and Applications on Round Genomes.

Area of Science:

• Computational Biology
• Bioinformatics
• Genomics

Background:

• Circular genomes are prevalent in bacteria, chloroplasts, and mitochondria.
• Identifying clusters of genetic or epigenetic marks on circular genomes is biologically significant.
• Existing K-means clustering methods are computationally intensive for large circular datasets.

Purpose of the Study:

• To develop a fast and optimal algorithm for circular data clustering.
• To address the computational limitations of existing methods for large circular datasets.
• To provide a robust tool for analyzing clustered data on circular genomes.

Main Methods:

• Developed a fast optimal circular clustering (FOCC) algorithm with O(KN log^2 N) time complexity.
• Integrated divide-and-conquer and bracket dynamic programming strategies for optimal framed clustering.
• Linearized circular data and utilized monotonic cluster borders for optimality.

Main Results:

• FOCC significantly outperforms brute-force and heuristic methods, achieving speedups of three orders of magnitude on 50,000 data points.
• Generated high-quality clusters of CpG sites and genes on circular genomes.
• The algorithm demonstrates subquadratic-time efficiency for various clustering types (circular, framed, angular, periodical, looped).

Conclusions:

• The FOCC algorithm provides a computationally efficient and optimal solution for circular data clustering.
• This advancement enables more effective analysis of genetic and epigenetic patterns on circular genomes.
• The R package 'OptCirClust' implements these novel algorithms, making them accessible to researchers.