权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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

利用分组测试和贝叶斯网络进行基因分析的有效汇集实验算法

基本信息

批准号：
15340035
负责人：
JIMBO Masakazu
金额：
$ 7.04万
依托单位：
Nagoya University (2004-2005)Keio University (2003)
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (B)
财政年份：
2003
资助国家：
日本
起止时间：
2003 至 2005
项目状态：
已结题

项目摘要

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.

在DNA文库筛选中，常常需要在大量的克隆中检测出对某些试验有阳性反应的克隆。为了减少试验次数，采用了混合试验。也就是说，我们生成一个克隆子集的集合，并测试每个这样的池。如果池的状态为正，则它至少包含一个正，否则，它不包含任何正。通过这种合并实验，我们可以减少实验的数量。但是实验结果可能会出现假阳性和假阴性，在本课题中，我们针对克隆筛选问题中的两个课题，注意到了假阳性和假阴性可能产生的错误。首先，我们开发了一些2-连续阳性可检测矩阵的结构，以检测线性有序克隆中的连续阳性，这些线性有序克隆在e=2和3时最多纠正e个错误。此外，提出了基于贝叶斯网络的与低密度奇偶校验码（LDPC）相关的有效正克隆检测算法。我们开发了两种算法，一种是基于信念传播的，另一种是基于凹凸方法。前一种算法在池化设计的坦纳图中不存在短圈时有效，后一种算法在池化设计的坦纳图中存在短圈时也有效.我们通过仿真实验检验了算法的检测能力和计算速度。该算法已获得专利，研究成果已在国际上发表或投稿。