Search

The MINIMUM-RECOMBINANT HAPLOTYPE CONFIGURATION problem (MRHC) has been highly successful in providing a sound combinatorial formulation for the important problem of genotype phasing on pedigrees. Despite several algorithmic advances that have improved the efficiency, its applicability to real data sets has been limited since it does not take into account some important phenomena such as mutations, genotyping errors, and missing data. In this work, we propose the MINIMUM-RECOMBINANT HAPLOTYPE CONFIGURATION WITH BOUNDED ERRORS problem (MRHCE), which extends the original MRHC formulation by incorporating the two most common characteristics of real data: errors and missing genotypes (including untyped individuals). We describe a practical algorithm for MRHCE that is based on a reduction to the well-known Satisfiability problem (SAT) and exploits recent advances in the constraint programming literature. An experimental analysis demonstrates the biological soundness of the phasing model and the effectiveness (on both accuracy and performance) of the algorithm under several scenarios. The analysis on real data and the comparison with state-of-the-art programs reveals that our approach couples better scalability to large and complex pedigrees with the explicit inclusion of genotyping errors into the model.

Mass Spectrometry (MS)-based technologies represent a promising area of research in clinical analysis. They are primarily concerned with measuring the relative intensity (i.e., signals) of many protein/peptide molecules associated with their mass-to-charge ratios. These measurements provide a huge amount of information which requires adequate tools to be interpreted. Following the methodology for testing hypotheses, we investigate the proteomic signals of the most common type of Renal Cell Carcinoma, the Clear Cell variant (ccRCC) [1]. By using mutual information, we detect changes in dependence values between signals from control to case groups (ccRCC or non-ccRCC). To this end, we sample and represent each population group through graphs, thus providing the observed dependence structures (many real domains are best described by relational models [2]). This way, graphs establish abstract frames of reference in our analysis giving the opportunity to test hypotheses over their properties. In other words, changes are detected by testing graph property modifications from group to group. We report the mass-to-charge values which identify bounded regions where changes have been detected. The main interest in handling such regions is to perceive which signal ranges are associated with some specific factors of interest (e.g., studying differentially expressed peaks between cases and controls) and thus, to suggest potential biomarkers for future analysis [3]. This study has been applied to samples collected at the "Ospedale Maggiore Policlinico" Foundation (Milano, Italy) using a standardized protocol. All samples were analyzed using an UltraFlex II MALDI-TOF/TOF MS instrument and mass spectra were acquired in the m=z range of 1000-12000. The samples cohort consists of 85 control subjects and 102 Renal Cell Carcinoma patients. It was possible to classify pathological group in patients affected by clear cell (ccRCC) and other different histological subtypes (respectively 79 ccRCC and 23 non-ccRCC). Table I reports the selected rejection regions (i.e., tests reject the null) at the 5% significance level. Testing hypotheses suggested by the data may induce statistical bias. For this reason, we evaluate the results to independent samples. We investigate whether test decisions are statistically independent from the region's property (i.e., distinguishing (DR) or non-distinguishing (ND) regions) when new samples are given. In other words, we want to know whether the property of a region can be statistically associated to test decisions when new samples are available. After that a new sample is provided, we verify test decisions over both the detected distinguishing regions and these regions out of the m=z bounding values previously detected. Table II summarizes the (Fisher's exact test) results confirming a significant association (a = 0.05 level) between decisions and region's property for both the class of tests. This work was supported by grants from the Italian Ministry of University and Research (PRIN n. 69373, FIRB n. RBRN07BMCT 011, FAR 2006 -- 2011), EuroKUP COST Action (BM0702) and the NEDD project ("Regione Lombardia").