The complexity of the overlap method for sequencing biopolymers

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Biopolymer sequence reconstruction from overlapping fragments is crucial for understanding biological functions.
• Current methods face computational intractability, limiting their universal applicability.
• The challenge lies in the combinatorial complexity of fragment assembly.

Purpose of the Study:

• To investigate the computational complexity of biopolymer sequence reconstruction.
• To identify conditions under which sequence reconstruction becomes computationally tractable.
• To develop efficient algorithms for determining unique biopolymer sequences.

Main Methods:

• Analysis of the computational complexity of overlap sequencing algorithms.
• Introduction of the concept of 'prime strings' as crucial known fragments.
• Application of graph theory for sequence reconstruction and validation.

Main Results:

• The general problem of overlap sequencing is proven to be computationally intractable.
• The introduction of prime strings transforms the problem into an efficiently solvable one.
• Graph theory enables counting consistent sequences and verifying uniqueness.

Conclusions:

• Overlap sequencing is generally intractable, necessitating alternative approaches.
• Prime string identification is key to efficient and reliable biopolymer sequence reconstruction.
• Graph-based methods provide a robust framework for sequence assembly and uniqueness assessment.