Centroid based clustering of high throughput sequencing reads based on n-mer counts

Area of Science:

• Computational Biology
• Bioinformatics
• Genomics

Background:

• Alignment-free sequence comparison is crucial for various computational biology problems.
• Sequence clustering is a common task that benefits from efficient comparison methods.
• This study applies alignment-free comparison, specifically using sequence composition, to address sequence clustering challenges.

Purpose of the Study:

• To evaluate alignment-free sequence clustering methods based on word counts.
• To assess the efficiency and accuracy of different clustering algorithms.
• To develop and provide an open-source tool for alignment-free sequence clustering.

Main Methods:

• Centroid-based clustering algorithms utilizing word counts were investigated.
• The performance of the k-means algorithm, with and without data whitening, was evaluated for computational efficiency.
• The soft expectation maximization method was employed to improve clustering accuracy by assigning probabilistic cluster memberships.

Main Results:

• The k-means algorithm demonstrated computational efficiency for sequence clustering.
• Soft expectation maximization yielded higher clustering accuracy compared to standard methods.
• An open-source tool for alignment-free clustering (afcluster) was implemented and made publicly available.

Conclusions:

• Alignment-free sequence clustering is valuable for high-throughput sequencing analysis, offering reduced resource requirements and minimal quality loss during assembly.
• The length of sequencing reads is a significant factor influencing the performance of alignment-free read clustering.
• The developed tool facilitates efficient and accurate alignment-free sequence clustering.