Fast exact algorithms for the closest string and substring problems with application to the planted (L, d)-motif...

Area of Science:

• Computational Biology
• Bioinformatics
• Algorithm Design

Background:

• The closest string and closest substring problems are fundamental in computational biology for identifying conserved sequence patterns.
• Existing algorithms often face computational challenges, especially with large datasets or complex biological sequences like DNA and proteins.
• Parameterized complexity offers a way to analyze and improve algorithm performance based on specific problem parameters, such as the number of mismatches.

Purpose of the Study:

• To develop novel parameterized algorithms for the closest string and closest substring problems.
• To significantly improve the time complexity of solving these problems for biological sequences.
• To experimentally validate the theoretical performance gains and compare with existing state-of-the-art methods.

Main Methods:

• Designed two parameterized algorithms for the closest string problem with improved time complexities for DNA and protein strings.
• Extended one algorithm to address the closest substring problem, incorporating parameterized complexity for enhanced efficiency.
• Implemented the algorithm in C and conducted experimental evaluations on the planted (L, d)-motif problem.

Main Results:

• Achieved substantial theoretical improvements in time complexity for both closest string and substring problems compared to previous bests.
• Experimental results demonstrate that the new algorithm runs faster than the PMSPrune program for practical and challenging cases.
• The implemented algorithm also showed reduced memory consumption, indicating greater efficiency.

Conclusions:

• The developed parameterized algorithms provide a more efficient computational approach for the closest string and substring problems.
• These algorithms offer practical advantages for biological sequence analysis, particularly in motif discovery tasks.
• The study confirms the effectiveness of parameterized complexity in advancing bioinformatics algorithm design.