Searching Genome-Wide Multi-Locus Associations for Multiple Diseases Based on Bayesian Inference.

Taking the advantage of high-throughput single nucleotide polymorphism (SNP) genotyping technology, large genome-wide association studies (GWASs) have been considered to hold promise for unraveling complex relationships between genotypes and phenotypes. Current multi-locus-based methods are insufficient to detect interactions with diverse genetic effects on multifarious diseases. Also, statistic tests for high-order epistasis ( ≥ 2 SNPs) raise huge computational and analytical challenges because the computation increases exponentially as the growth of the cardinality of SNPs combinations. In this paper, we provide a simple, fast and powerful method, named DAM, using Bayesian inference to detect genome-wide multi-locus epistatic interactions in multiple diseases. Experimental results on simulated data demonstrate that our method is powerful and efficient. We also apply DAM on two GWAS datasets from WTCCC, i.e., Rheumatoid Arthritis and Type 1 Diabetes, and identify some novel findings. Therefore, we believe that our method is suitable and efficient for the full-scale analysis of multi-disease-related interactions in GWASs.

On the parameterized complexity of pooling design.

Pooling design is a very helpful tool for reducing the number of tests in DNA library screening, which is a key process to obtain high-quality DNA libraries for studying gene functions. Three basic problems in pooling design are, given an m x n binary matrix and a positive integer d, to decide whether the matrix is d-separable (d-separable, or d-disjunct). The three problems are all known to be coNP-complete. Since in most applications, d is a small integer compared to n, it is interesting to investigate whether there are efficient algorithms solving the above problems when the value of d is small. In this article, we give a negative answer to the above question by studying the parameterized complexity of these three problems, with d as the parameter. We show that the parameterized versions of all the three problems are co-W[2]-complete. An immediate implication of our results is that, given an m x n binary matrix and a positive integer d, a deterministic algorithm with running time f(d) x (mn)(O(1)) (where f is an arbitrary computable function) to decide whether the matrix is d-separable (d-separable, or d-disjunct) should not be expected.

New constructions of one- and two-stage pooling designs.

The study of gene functions requires a DNA library of high quality, such a library is obtained from a large mount of testing and screening. Pooling design is a very helpful tool for reducing the number of tests for DNA library screening. In this paper, we present new one- and two-stage pooling designs, together with new probabilistic pooling designs. The approach in this paper works for both error-free and error-tolerance scenarios.

Efficient constructions of disjunct matrices with applications to DNA library screening.

The study of gene functions requires a DNA library of high quality, such a library is obtained from a large mount of testing and screening. Pooling design is a very helpful tool for reducing the number of tests for DNA library screening. In this paper, we present two Las Vegas algorithms for efficient constructions of d-disjunct and (d ; z)-disjunct matrices respectively. These new constructions can be directly applied to construct error-free and error-tolerant pooling designs.

New construction for transversal design.

The study of gene functions requires the development of a DNA library of high quality through much of testing and screening. Pooling design is a mathematical tool to reduce the number of tests for DNA library screening. The transversal design is a special type of pooling design, which is good in implementation. In this paper, we present a new construction for transversal designs. We will also extend our construction to the error-tolerant case.

Identifying d positive clones in the presence of inhibitors.

Farach et al. introduced the inhibitor model in pooling design, where existence of a single inhibitor clone in a pool dictates its outcome to be negative regardless of the existence of positive clones in the pool. Various sequential or multiround pooling designs have been given to identify all the positive clones under the inhibitor model. Recently, Hwang and Liu gave a (one round) pooling design for the inhibitor model which is error tolerant. More specifically, suppose the set of n clones to be screened contains up to d positive clones, up to r inhibitors and the pooling experiments can generate up to e errors, they show that a (d + r + 2e)-disjunct matrix does the job. In this paper, we give a pooling design for the case that among n clones exactly d are positive. We reduce the requirement of (d + r + 2e)-disjunctness to (d + r + e)-disjunctness, which would mean the saving of many pools. We also show how our design can be used to identify all positive clones when their number is, at most, d.