A statistical method for alignment-free comparison of regulatory sequences

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Traditional sequence similarity assessment relies on alignment, which is insufficient for non-orthologous or diverged cis-regulatory sequences.
• Identifying functional relationships in such sequences necessitates alignment-free similarity measures.

Purpose of the Study:

• To investigate a novel alignment-free sequence comparison score based on word frequencies.
• To develop an efficient method for calculating this score with quadratic time complexity improvement.
• To evaluate the score's efficacy in identifying functional relationships among cis-regulatory modules.

Main Methods:

• Developed a novel score that compares frequencies of all fixed-length words within sequences.
• Implemented an efficient algorithm for score calculation, achieving quadratic time complexity improvement over naive methods.
• Evaluated the score's performance on tissue-specific cis-regulatory modules from Drosophila and human.

Main Results:

• The novel score successfully discriminates functionally related cis-regulatory sequences from unrelated pairs.
• The score is comparable across sequence pairs with arbitrary background distributions.
• Performance evaluation showed the score consistently outperformed five other alignment-free similarity measures.

Conclusions:

• The novel alignment-free score is a powerful tool for identifying functional relationships between divergent cis-regulatory sequences.
• The developed method offers significant computational efficiency.
• The score's superior performance validates its utility in comparative genomics and regulatory element analysis.