Efficient algorithms of pooling experiments for gene analysis by utilizing group testing and Bayesian network

点击翻译按钮获取中文摘要

In DNA library screening, it is often required to detect clones with positive response for some test among a huge amount of clones. In order to reduce the number of tests, pooling experiment is adapted. That is, we generate a collection of subsets of clones and test each of such pools. If the state of a pool is positive, it contains at least one positive, otherwise, it does not contain any positives. By this pooling experiment we can reduce the number of experiments. But the results of tests may contain false positive and false negative.In our project we focused two subjects of clone screening problem by noting the possible errors of false positive/negative. Firstly, we developed some constructions of 2-consecutive positive detectable matrices to detect consecutive positives among linearly ordered clones which correct at most e errors for e=2 and 3. Moreover efficient algorithms for detecting positive clones is proposed, which are based on Bayesian network and are related to low density parity check codes (LDPC). We developed two algorithms, one is based on the belief propagation and another is based on the convex-concave method. The former algorithm is efficient when the Tanner graph of a pooling design has no short cycles, while the latter one is useful even when there are short cycles in the Tanner graph. We examined the detectability and computing speed of our algorithm by simulation. We got a patent for the former algorithm and the results obtained by this research has been published or submitted to some international journals.