Tabusearch

Tabusearch applies a tabu search heuristic to optimize isothermic DNA sequencing by hybridization (SBH) by constructing high-quality suboptimal oligonucleotide libraries with uniform melting temperatures.

Key Features:

• Isothermic Libraries: Uses oligonucleotide libraries with equal melting temperatures calculated by assigning 2°C per adenine (A) or thymine (T) and 4°C per cytosine (C) or guanine (G).
• Error Reduction: Uniform melting temperatures reduce temperature-dependent variability and thereby minimize errors in hybridization experiments.
• Heuristic Algorithm: Incorporates a tabu search heuristic to address the computational challenges of SBH and to handle both positive and negative errors.
• Suboptimal Solutions: Focuses on constructing computationally feasible high-quality suboptimal solutions when optimal solutions are intractable.

Scientific Applications:

• DNA sequencing by hybridization (SBH): Supports SBH workflows using isothermic oligonucleotide libraries to improve hybridization-based sequencing accuracy.
• Genomic sequencing and computational experiments: Handles positive and negative errors and scales to large datasets for sequencing complex genomes and extensive computational evaluations.

Methodology:

Tabusearch applies tabu search to systematically explore the solution space while avoiding previously visited suboptimal paths and constructs high-quality suboptimal solutions for isothermic SBH.