Exact and Heuristic Approaches for Identifying Disease-Associated SNP Motifs
Gaofeng Huang, Peter Jeavons and Dominic Kwiatkowski abstract
A Single Nucleotide Polymorphism (SNP) is a small DNA variation which occurs naturally between different individuals of the same species. Some combinations of SNPs in the human genome are known to increase the risk of certain complex genetic diseases. This paper formulates the problem of identifying such disease-associated SNP motifs as a combinatorial optimization problem and shows it to be NP-hard. Both exact and heuristic approaches for this problem are developed and tested on simulated data and real clinical data. Computational results are given to demonstrate that these approaches are sufficiently effective to support ongoing biological research.
infobook title | Proceedings of 5th Asia-Pacific Bioinformatics Conference, APBC 2007 |
isbn | 978-1-86094-783-4 |
pages | 175-184 |
publisher | Imperial College Press |
series | Advances in Bioinformatics and Computational Biology |
volume | 5 |
year | 2007 |
links
BibTeX
related pages
|
