Sequencing-by-hybridization at the information-theory bound: an optimal algorithm.

Area of Science:

• Genomics
• Bioinformatics
• Molecular Biology

Background:

• The standard oligomer probe scheme for DNA sequencing by hybridization (SBH) has limitations in sequence reconstruction.
• A novel gapped-probe scheme combining natural and universal bases was previously introduced, showing improved performance over standard methods.

Purpose of the Study:

• To present and analyze a new, more powerful sequencing algorithm specifically designed for the gapped-probe SBH scheme.
• To demonstrate that the new algorithm achieves near information-theory bound performance for SBH.

Main Methods:

• Development and theoretical analysis of a novel sequencing algorithm for the gapped-probe SBH scheme.
• Mathematical proof demonstrating the algorithm's efficiency and performance bounds.

Main Results:

• The new algorithm significantly enhances the capabilities of the gapped-probe SBH scheme.
• The algorithm achieves high-confidence performance within a small constant factor (approximately 2) of the information-theory bound.
• The algorithm maintains a running time linear in the target sequence length.

Conclusions:

• The developed algorithm represents a substantial advancement in SBH technology.
• This algorithm maximizes the potential of the gapped-probe scheme, offering efficient and accurate DNA sequencing.
• The findings pave the way for more effective DNA sequencing by hybridization applications.