Related Experiment Videos
Towards optimally multiplexed applications of universal arrays
Amir Ben-Dor1, Tzvika Hartman, Richard M Karp
1Agilent Laboratories, 395 Page Mill Road, Palo Alto, CA 94303, USA.
Summary
This study addresses DNA genotyping array design by minimizing assay-specific cross-hybridization. An efficient O(d)-approximation algorithm is developed for optimizing experimental configurations, improving accuracy in single nucleotide polymorphism (SNP) detection.
Area of Science:
- Bioinformatics
- Computational Biology
- Genomics
Background:
- Cross-hybridization in DNA arrays can arise from universal or assay-specific components.
- Previous work focused on optimizing universal array components to prevent cross-hybridization.
Purpose of the Study:
- To identify the most economical experimental configuration of assay-specific components that avoids cross-hybridization.
- To develop efficient algorithms for optimizing DNA tag array design for single nucleotide polymorphism (SNP) genotyping.
Main Methods:
- The problem is formalized as covering vertices of a bipartite graph with minimum balanced subgraphs of maximum degree 1.
- An O(d)-approximation algorithm is developed for cases where vertex degrees are bounded by d.
- A stochastic model is used to establish a lower bound on the cover size.
Main Results:
- The general problem of minimizing cross-hybridization is NP-complete.
- An O(d)-approximation algorithm is presented for practical biological settings with bounded degrees.
- A variant requiring vertex-disjoint covering subgraphs also achieves an O(d)-approximation.
Conclusions:
- Efficient algorithms can mitigate assay-specific cross-hybridization in DNA genotyping.
- The developed approximation algorithms provide practical solutions for optimizing SNP detection arrays.
- Theoretical analysis and heuristic implementations support the effectiveness of the proposed methods.