Two combinatorial optimization problems for SNP discovery using base-specific cleavage and mass spectrometry
The discovery of single-nucleotide polymorphisms (SNPs) has important implications in a variety of genetic studies on human diseases and biological functions. One valuable approach proposed for SNP discovery is based on base-specific cleavage and mass spectrometry. However, it is still very challeng...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2013
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/105219 http://hdl.handle.net/10220/16762 |
| _version_ | 1811693456468213760 |
|---|---|
| author | Chen, Xin Wu, Qiong Sun, Ruimin Zhang, Louxin |
| author2 | School of Physical and Mathematical Sciences |
| author_facet | School of Physical and Mathematical Sciences Chen, Xin Wu, Qiong Sun, Ruimin Zhang, Louxin |
| author_sort | Chen, Xin |
| collection | NTU |
| description | The discovery of single-nucleotide polymorphisms (SNPs) has important implications in a variety of genetic studies on human diseases and biological functions. One valuable approach proposed for SNP discovery is based on base-specific cleavage and mass spectrometry. However, it is still very challenging to achieve the full potential of this SNP discovery approach.
In this study, we formulate two new combinatorial optimization problems. While both problems are aimed at reconstructing the sample sequence that would attain the minimum number of SNPs, they search over different candidate sequence spaces. The first problem, denoted as SNP - MS P , limits its search to sequences whose in silico predicted mass spectra have all their signals contained in the measured mass spectra. In contrast, the second problem, denoted as SNP - MS Q , limits its search to sequences whose in silico predicted mass spectra instead contain all the signals of the measured mass spectra. We present an exact dynamic programming algorithm for solving the SNP - MS P problem and also show that the SNP - MS Q problem is NP-hard by a reduction from a restricted variation of the 3-partition problem.
We believe that an efficient solution to either problem above could offer a seamless integration of information in four complementary base-specific cleavage reactions, thereby improving the capability of the underlying biotechnology for sensitive and accurate SNP discovery. |
| first_indexed | 2024-10-01T06:51:58Z |
| format | Journal Article |
| id | ntu-10356/105219 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T06:51:58Z |
| publishDate | 2013 |
| record_format | dspace |
| spelling | ntu-10356/1052192023-02-28T19:45:36Z Two combinatorial optimization problems for SNP discovery using base-specific cleavage and mass spectrometry Chen, Xin Wu, Qiong Sun, Ruimin Zhang, Louxin School of Physical and Mathematical Sciences DRNTU::Science::Biological sciences::Biomathematics The discovery of single-nucleotide polymorphisms (SNPs) has important implications in a variety of genetic studies on human diseases and biological functions. One valuable approach proposed for SNP discovery is based on base-specific cleavage and mass spectrometry. However, it is still very challenging to achieve the full potential of this SNP discovery approach. In this study, we formulate two new combinatorial optimization problems. While both problems are aimed at reconstructing the sample sequence that would attain the minimum number of SNPs, they search over different candidate sequence spaces. The first problem, denoted as SNP - MS P , limits its search to sequences whose in silico predicted mass spectra have all their signals contained in the measured mass spectra. In contrast, the second problem, denoted as SNP - MS Q , limits its search to sequences whose in silico predicted mass spectra instead contain all the signals of the measured mass spectra. We present an exact dynamic programming algorithm for solving the SNP - MS P problem and also show that the SNP - MS Q problem is NP-hard by a reduction from a restricted variation of the 3-partition problem. We believe that an efficient solution to either problem above could offer a seamless integration of information in four complementary base-specific cleavage reactions, thereby improving the capability of the underlying biotechnology for sensitive and accurate SNP discovery. NMRC (Natl Medical Research Council, S’pore) Published version 2013-10-24T06:01:24Z 2019-12-06T21:47:36Z 2013-10-24T06:01:24Z 2019-12-06T21:47:36Z 2012 2012 Journal Article Chen, X., Wu, Q., Sun, R., & Zhang, L. (2012). Two combinatorial optimization problems for SNP discovery using base-specific cleavage and mass spectrometry. BMC Systems Biology, 6(Suppl 2). 1752-0509 https://hdl.handle.net/10356/105219 http://hdl.handle.net/10220/16762 10.1186/1752-0509-6-S2-S5 23282116 168381 en BMC systems biology © 2012 Chen et al.; licensee BioMed Central Ltd. This article is published under license to BioMed Central Ltd. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. application/pdf |
| spellingShingle | DRNTU::Science::Biological sciences::Biomathematics Chen, Xin Wu, Qiong Sun, Ruimin Zhang, Louxin Two combinatorial optimization problems for SNP discovery using base-specific cleavage and mass spectrometry |
| title | Two combinatorial optimization problems for SNP discovery using base-specific cleavage and mass spectrometry |
| title_full | Two combinatorial optimization problems for SNP discovery using base-specific cleavage and mass spectrometry |
| title_fullStr | Two combinatorial optimization problems for SNP discovery using base-specific cleavage and mass spectrometry |
| title_full_unstemmed | Two combinatorial optimization problems for SNP discovery using base-specific cleavage and mass spectrometry |
| title_short | Two combinatorial optimization problems for SNP discovery using base-specific cleavage and mass spectrometry |
| title_sort | two combinatorial optimization problems for snp discovery using base specific cleavage and mass spectrometry |
| topic | DRNTU::Science::Biological sciences::Biomathematics |
| url | https://hdl.handle.net/10356/105219 http://hdl.handle.net/10220/16762 |
| work_keys_str_mv | AT chenxin twocombinatorialoptimizationproblemsforsnpdiscoveryusingbasespecificcleavageandmassspectrometry AT wuqiong twocombinatorialoptimizationproblemsforsnpdiscoveryusingbasespecificcleavageandmassspectrometry AT sunruimin twocombinatorialoptimizationproblemsforsnpdiscoveryusingbasespecificcleavageandmassspectrometry AT zhanglouxin twocombinatorialoptimizationproblemsforsnpdiscoveryusingbasespecificcleavageandmassspectrometry |