Dataset Information

Two combinatorial optimization problems for SNP discovery using base-specific cleavage and mass spectrometry.

ABSTRACT:

Background

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.

Results

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 - MSP, 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 - MSQ, 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 - MSP problem and also show that the SNP - MSQ problem is NP-hard by a reduction from a restricted variation of the 3-partition problem.

Conclusions

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.

SUBMITTER: Chen X

PROVIDER: S-EPMC3521188 | biostudies-literature | 2012

REPOSITORIES: biostudies-literature

ACCESS DATA

Publications

Two combinatorial optimization problems for SNP discovery using base-specific cleavage and mass spectrometry.

Chen Xin X Wu Qiong Q Sun Ruimin R Zhang Louxin L

BMC systems biology 20121212

<h4>Background</h4>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.<h4>Results</h4>In this study, we formulate two new combinatorial optimization problems. While both problems are aim ...[more]

PMID: 23282116

Similar Datasets

Project description:A method of analysis is presented that utilizes matrix-assisted laser desorption/ionization-time of flight mass spectrometry (MALDI-TOF MS) to monitor the kinetics and products of RNA cleavage, by use of a program designed to mass-match observed MS peaks with predicted RNA cleavage products. The method is illustrated through application to the study of targeted oxidation of RNA stem loops from HIV-1 Rev Response Element mRNA (RRE RNA) and ribosomal 16S A-site RNA (16S RNA) by metallonucleases. Following incubation of each RNA with catalysts and/or redox co-reactants, reaction mixtures were desalted, and MALDI-TOF MS was used to monitor both time-resolved formation of cleavage products and disappearance of full-length RNA. For each RNA, a unique list was generated that contained the predicted masses of both the full-length, and all of the possible RNA cleavage fragments that resulted from the combination of all possible cleavage sites and each of the six expected overhangs formed at nascent termini adjacent to the cleavage sites. The overhangs corresponded to 2',3'-cyclic phosphate, 3'-phosphate, 3'-phosphoglycolate, 5'- hydroxyl and 5'- phosphate, which corresponded to differing oxidative, hydrolytic, and/or 2'-OH-mediated-endonucleolytic modes of scission. Each mass spectrum was compared with a corresponding list of predicted masses, and peaks were rapidly assigned by use of a Perl script, with a mass-matching tolerance of 200 ppm. Both time-dependent cleavage mediated by metallonucleases and MALDI-TOF-induced fragmentation were observed, and these were distinguished by time-dependent experiments. The resulting data allowed a semi-quantitative assessment of the rate of formation of each overhang at each nucleotide position. Limitations included artifactual skewing of quantification by mass bias, a limited mass range for quantification, and a lack of detection of secondary cleavage products. Nevertheless, the method presented herein provides a rapid, accurate, highly-detailed and semi-quantitative analysis of RNA cleavage that should be widely applicable.

Dataset Information

Two combinatorial optimization problems for SNP discovery using base-specific cleavage and mass spectrometry.

Background

Results

Conclusions

Publications

Two combinatorial optimization problems for SNP discovery using base-specific cleavage and mass spectrometry.

Similar Datasets

OmicsDI is part of the ELIXIR infrastructure