Optimal pooling for genome re-sequencing with ultra-high-throughput short-read technologies

Area of Science:

• Genomics
• Bioinformatics
• Computational Biology

Background:

• Next-generation sequencing (NGS) technologies, like Solexa, enable high-throughput re-sequencing of bacterial artificial chromosome (BAC) clones.
• Accurate re-sequencing of BACs is crucial for identifying fine-scale genomic differences relative to a reference genome.
• Multiplexing BAC sequencing via pooling offers cost-effectiveness but introduces analytical challenges due to shared subsequences.

Purpose of the Study:

• To develop an optimal experimental design strategy for multiplexed BAC re-sequencing using Solexa technology.
• To address the challenge of pooling BACs to minimize downstream data analysis complications arising from common subsequences.
• To improve the efficiency and accuracy of re-sequencing studies involving BAC clones.

Main Methods:

• Utilized combinatorial optimization techniques, specifically approximation algorithms for the max n-cut and max n-section problems on hypergraphs.
• Developed a novel experimental design strategy for pooling BACs in high-throughput re-sequencing experiments.
• Applied the developed algorithms to sample cases to evaluate performance against random partitioning.

Main Results:

• The proposed experimental design strategy significantly improves the performance of BAC re-sequencing experiments.
• Achieved more than a 2-fold performance improvement compared to random partitioning of BACs for sequencing.
• Demonstrated the effectiveness of combinatorial solutions in optimizing multiplexed sequencing experiments.

Conclusions:

• The developed combinatorial strategy offers a superior approach for designing BAC pooling in re-sequencing studies.
• This method enhances the efficiency and cost-effectiveness of high-throughput sequencing projects.
• Optimized experimental design is critical for maximizing the utility of NGS technologies in genomic research.