（基础数学专业论文）关于复形的一些pooling设计.pdf

摘要 本文把p o o l i n g 设计中在测试结果理想的情况下得到的某些结论推广到了可以容错 的情形；把阳性对象是单个集的情形下得到的某些结论推广到了阳性对象是一复形 ( h 后) 的情形首先在q a l m o s t 七一d i s j u n c t 矩阵的基础上引入了a a l m o s t ( 七；2 e + 1 ) 一s 印o r 0 6 f e 矩阵的概念，用它的补阵与随机行取交得到的新矩阵构作了一个关于七一 复形的容错的p o o l i n g 设计，并计算了检测出所有阳性七一复形的数学期望然后引入了 口一a l m o s t 七e d i s j u n c t 矩阵的概念，用它的补阵与随机行取交得到的新矩阵构作了一个关 于h 一复形的容错的p o o l i n g 设计，并计算了检测出所有阳性七l 一复形的数学期望最 后利用( s ，z ) 一叠加码所对应的矩阵给出了适用于所有关于七l 一复形的i 佗胁6 i 亡卯模型的 p o o l i n g 设计利用( s ，f ) 8 一自由覆盖族所对应的矩阵，给出了在关于七l 一复形的 扎加6 沈卯 模型中可以容错的p o o l i n g 设计在( d + ( m 伽zd ，r ) ) 一比s j 札n c t 矩阵的基础上引入了 ( 七，d + ( m 俐td ，r ) ) 一叠加码的概念，用它对应的矩阵构作了一个在m i n 肮阮计模型 中检测阳性七l 一复形的p o o l i n g 设计 关键词：p o o l i n g 设计复形s e p a r a b l e 矩阵d i s j u n c t 矩阵i n h i b i t o r 自由覆盖族 叠加码 i i i a b s t r a c t i nt h i sp a p e r w eg e n e r a l i z et h er e s u l tw h i c hi sd e r i v e di nt h ec o n d i t i o nt h a tt h et e s to u t c o m ei si d e a li np o o l i n gd e s i g nt ot h ee r r o r - t o l e r a n tv e r s i o n a n dw eg e n e r a l i z et l l er e s u l t w h i c hi sd e r i v e di nt h ec o n d i t i o nt h a tt h ep o s i t i v ee l e m e n ti ss i n g l et ot h ev e r s i o nt h a tt h e p o s i t i v ee l e m e n ti s 七1 一c o m p l e x ( 七1尼) f i r s t l y w ep r o p o s et h ed e 矗n i t i o no fq a l m o s t ( 七；2 e + 1 ) 一s 印a r a b l em a t r i xo nt h eb a s eo f 口一a j m o s t 尼一d i s j u n c tm a t r i x w - eu s et h em a t r i x w h i c hr e s u l t sb yt h ec o m p l e m e n to f t h e 口一a l m o s t ( 七；2 e + 1 ) 一s 印口r n 6 f em a t r i xi n t e r s e c t i n g r a n d o mr o w st 0c o n s n l l c t 卸e 啪卜t o l e r a n tp o o l i n gd e s i g nf o r 七一c d 唧f e z e s a n dw ec a l c u l a t e t h ee x p e c t e dn u m b e ro fi d e n t i 锣i n ga l lp o s i t i v e 七一c ( ，仃印z e z e s n e x t ，w ep r o p o s et h ed e f i n i t i o n o fq a l m o s t 七e d i s j u n c tm a t r i x w eu s em em a t r i xw h i c hr e s u l t sb yt h ec o m p l e m e n to fm e q a l m o s t 尼8 一d i s j u n c tm a 砸xi n t e r s e c t i n gr a n d o mr o w st oc o n s t r u c ta ne r r o r - t o l e r a n tp o o l i n g d e s i g nf 0 r 七l c d 唧z e z e s a n dw ec a l c u l a t et h ee x p e c t e dn u m b e ro fi d e n t i f y i n ga l lp o s i t i v e 尼l c d 叫e z e s f i n a l l y w eu s et h em 枷xo f ( s ，z ) 一s u p e r i m p o s e dc o d et og i v eap o o l i n g d e s i g nw h i c h f i t sa l li n h i b i t o rm o d e l sf o r 七l c d m 讲e z e s w 色u s et h em a t r i xo f ( s ，f ) 8 一c o v c r 疗e ef a m i l yt 0g i v e 卸e 玎0 卜t o l e r 卸tp o o l i n gd e s i g ni nt h ei n h i b i t o rm o d e l f o r 七l c d m 州e z e s w ep i 。o p o s et h ed e f j n i t i o no f ( 七，d + ( 7 no u td ，7 ) ) 一s u p e r i m p o s e dc o d eo nt h eb a s eo f ( d + ( md u zd ，7 ) ) 一d i s j u n c tm a t r i x w 色u s et h em a 嫡xo f ( 七，d + ( md 札d ，7 ) ) 一s u p e r i m p o s e d c o d et i dg i v eap o o l i n gd e s i g nf o r 七l c d ，n p f e z e s k e y w o r d s ：p o o l i n gd e s i g n c o m p l e xs 印a f a b l em a t r i xd i s j u n c tm a t f i x i n h i b i t o r c o v e rf e ef a m i l y s u p e r i m p o s e dc o d e i v 学位论文原刨性声明 本人所提交的学馕论文关于复形的些p 0 0 1 i n g 设计，是在导师的指导下，独 立进行研究工作所取得的原创性成果。除文中已经注明引用的内容外，本论文不包含任 何其他个入或集体已经发表或撰写过的研究成果。对本文的研究做出重要贡献的个人和 集体，均已在文中标翡。 本声骥的法律后果蠢本入承担。 论文作者( 签名) ：脚东螂址 伽。2 年y 月6 同艺嚣嚣篇剿 凇n 萝年，月占同 v 叫 学位论文版权使用授权书 本学位论文作者完全了解河北师范大学有权保留并向豳家有关部门或机构送交学 位论文的复印秸鞠磁盘，允许论文被燕阒和借阕。本入授权河i l ：师范大学面以将学像论 文赡全帮或部分内容编入有关数据库进行检索，可以采爝影印、缩印葳其它复制手段傈 存、瓤7 ：编学俺论文。 ( 保密的学位论文在年解密后适用本授权书) 论文作者( 签名) ： 邳南韬扯 指导教师( 签名) ： 黝嵋 伽o 年y 月阿 秒彤年，j6 r ，l，心 引言 分组测试理论起源于二战期间为了确定n 个血样中哪些血样含有病毒的问题后来 由于在化学渗透试验，电子检验，码，多路存取信道传递，分子生物学和艾滋病筛选等方面 的应用【l 】【2 】【3 】而得以盛行 按照使用模型的不同，分组测试可以分为组合分组测试( c g t ) 和概率分组测试( p g t ) 两类按照试验步骤的不同，分组测试又可以分为时序算法和非适应性算法两类时序算 法指对被测对象一个挨一个地进行试验，允许后面试验使用前面所有试验的输出结果非 适应性算法是指所有试验同时进行，不允许一个试验使用其它试验的输出结果介于两个 算法之间的还有一个s 一部算法，这种算法的每一步中所作的试验同时进行，但每两步之 间是时序的两步算法是最接近非适应性算法的特别地，最后一步是单个的对象时，叫做 平凡两步算法 下面介绍一下组合分组测试的基础知识假定有n 个被测对象，它们或者是阴性的( 正 常的) ，或者是阳性的( 有缺陷的) ，同时阳性对象的个数不超过整数d ，目标是用尽量少的 试验检测出所有阳性对象将全部n 个被测对象分成若干子集，分别对每个子集加以检测 若输出结果为阴性，说明这个子集中所有被测对象都是阴性的，否则说明子集中至少有一 个是阳性 构作非适应性算法的试验是非常困难的因为对一个给定的对象个数n ，我们通常并 不知道是否存在不超过t 个p o o l s 的p o o l i n g 设计针对这个问题提出了对所有n 和所有t 都存在的随机p o o l i n g 设计【4 】尽管随机p o o l i n g 设计不能检测出所有阳性对象，但是它能 够计算不能检测出某个给定的阳性对象的概率，并且能够计算检测出所有阳性对象的概 率 由于多方面的原因，在试验的输出结果中出现错误是在所难免的因此构作容错的 d i s j u n c t 矩阵是非常必要的，即能容错的p 0 0 l i n g 设计【5 】- 构作容错和纠错能力强的分组试 验是非适应性分组测试的中心问题之一 在分组测试的试验中，有时只有某些对象放在一起才呈现阳性的特性，因此单个的阳 性对象集被阳性复形集所代替，即d = d 。，现，仇 ，其中每个d 称为一个阳性复 形( c d m p f e z ) 并且对t j ，通常假设d 垡岛1 6 】t 0 m e y 第一次给出了真核d n a 复制和 r a n 翻译的复形的例子【7 】在关于复形的分组测试中，试验结果是阳性的，说明这个试验 至少包含一个阳性复形 在分组测试的某些应用中，有些特殊的阴性对象可以消除阳性对象对试验结果的影 响这些对象被称为i n 九e 统d r f 8 】不同的i n l 溉d r 模型对试验结果有不同的影响作用例 如：最简单的饥m 觇t o r 模型是在一个试验中只要有1 个饥m 觇t 钟就会使结果由阳性变为 阴性【9 】m i 凡肮阮甜模型是在试验中至少包含m 个讯m 阮d r 才能把阳性试验结果变为 阴性【1 0 】研究在各种i n 胁阮d r 模型中检测所有阳性对象的问题是非常重要的 关于容错的模型的发展概况：1 9 6 4 年，w h k a u t z 和r r s i n g l e t o n 给出了检错和 纠错码的构作方法【3 】在 1 1 】和【1 2 】中1 a y u a nh u a n g 和c h i h w e nw 醯g 说明了一个 d 。一以s j u n c t 矩阵能够检测出实验结果中的e 个错误，纠正【e 21 个错误，并给出了一种 检错和纠错的方法2 0 0 6 年，a g d y a c h k o v ，a j m a c u l a 和p a l e n k i n 证明了把两步算 法用到d e 一班巧u 死d 矩阵中可以纠正实验结果中e 个错误【1 3 1 在【1 4 】中d z d u 和f k h w a i l g 说明了( d ；名) 一s 印n 7 口6 f e 矩阵可以纠正实验结果中的【( z 一1 ) 2 j 个错误 关于复形的两个随机p o o l i n g 设计：2 0 0 4 年，a j m a c u l a ，v ：v r y k o v 和s y e l 【i l 柚i n 用a a l m o s t 七一d i s j u n c t 矩阵的补阵与随机行取交得到的新矩阵构作了一个关于七一复形 的随机p o o l i n g 设计，并计算了在测试结果理想的情况下检测出所有阳性七一复形的数学 期望【1 5 】2 0 0 4 年，a j m a c u l a 和l j p 0 p y a c k 构作了一个关于七l 一复形( 七1 七) 的随 机p 0 0 l i n g 设计，并计算了在测试结果理想的情况下检测出所有阳性七一复形的数学期望 1 1 6 】而这些测试都是不能容错的 关于i n h i b i t o r 模型的发展概况：2 0 0 1 年，a g d y a c h k o v a j m a c u i a ，d c t o r n e y 和 p a v i l l e n k i n 给出了关于1 一i 死胁觇d 7 模型的p o o l i n g 设计【1 7 1 2 0 0 3 年，f k h w 卸g 和y c l i u 把它推广到了容错的情形【1 8 】2 0 0 7 年，f k h w 硼g 和f h c h 醐g 用( d + r ) 一班叮u n 甜 矩阵给出了适合所有 礼肮阮w 模型的p o o l i n g 设计，用( d + ，) d 十e 一班巧t n d 矩阵给出了 适合所有i n 觚跣t 卯模型的容错的p o o l i n g 设计，并用( d + ( 仇础亡吖r ) ) 一如耵t l n 以矩阵 给出了一个在m i n 肮觇芒d r 模型中检测阳性对象的p 0 0 l i n g 设计【8 】而这些都没有给出 关于复形的i n 胁6 锨钟模型的p o o l i n g 设计 本文把【1 5 】和【1 6 】中在测试结果理想的情况下得到的结论推广到了可以容错的情 形把【8 】中在阳性对象是单个集的情形下得到的结论推广到了阳性对象是七一复形 ( h 忌) 的情形首先在a a l m o s t 七一d i s j u n c t 矩阵的基础上引入了q a l m o s t ( 七；2 e + 1 ) 一s 印口r 0 6 f e 矩阵的概念，用它的补阵与随机行取交得到的新矩阵构作了一个关于七一 复形的容错的p o o l i n g 设计，并计算了检测出所有阳性七一复形的数学期望然后引入了 q a l m o s t 七。一d i s j u n c t 矩阵的概念，用它的补阵与随机行取交得到的新矩阵构作了一个关 予七l 一复形的容错的p o o l i n g 设计，并计算了检测出所有阳性七l 一复形的数学期望最 后利用( s ，z ) 一叠加码所对应的矩阵给出了适用于所有关于忌l 一复形的t n 胁跣凹模型的 p 0 0 l i n g 设计利用( s ，f ) 。一自由覆盖族所对应的矩阵。给出了在关于h 一复形的i 几舷6 赶卯 2 1 预备知识 1 1 符号与基本概念 定义1 1 1 【1 5 】令t 是一个正整数，记吲= 1 ，2 ，咄设s 是一个集合，集合s 中的 元素个数用i s i 表示 定义1 1 2 f 1 5 】嘲的子集中元素个数为k 的集合叫做一个七一集 定义1 1 3 【1 5 】设r = s l ，一，岛，& ) 为阳性复形集如果i & l = 七( 1 l d ) ，则 每个& 叫做一个七一复形 定义1 1 4 【1 5 】设a 是( 0 ，1 ) 一矩阵，在a 中互换o 和l 得到的新的矩阵称为a 的补阵 定义1 1 5 【1 5 】称有n 个分量的二元向量为佗一向量 定义1 1 6 【1 5 】给定礼一向 x 定义1 1 8 ( 1 l 】给定( o ，1 ) 一矩阵a ，任取a 的d + 1 列岛，c l ，o ，任意指定其中一 d 列，不妨设为g ，若至少有e + 1 个l 在岛而不在ug 中，则称a 为d e 一也町札n 以矩阵 t = l 例如： m = 10 0 10 0 010 0lo 0 01 0 01 是一个2 1 一饿巧让n 历矩阵 注记1 1 9 f l l 】一个d e 一班巧u n 以矩阵必然是一个r ：一砒町u 扎c 矩阵( r d ，z e ) 例中的矩阵也是一个1 1 一班町u n d 矩阵 定义1 1 1 0 【2 】给定n 一向量x ，y ， x = ( z l ，z ，z n ) ，y = ( l ，玑，) 用m k 瓠) i 表示x 与y 的h a m m i n g 距离且记为日( x ，y ) 定义1 1 1l 【1 4 】给定( 0 ，1 ) 一矩阵a 如果a 的任意两个d 列集的并的h a m m i n g 距离 至少是z ，则称a 为( d ；z ) 一s 印凹口6 z e 矩阵 例如： m = l0 0 0 10 0 0 0l0 o 01o 0 0 0l0 0 010 0 o 01 o 0 01 是一个( 3 ；2 ) 一s e 舯r 0 6 f e 矩阵 定义1 1 1 2 【l l 】对一个o ，l 矩阵a ，把某一列中分量是l 的所有行指标看作一个集合 那么对矩阵a 的两个列向量x 和y ， x = ( z l ，z t ，z n ) 。，y = ( 暑l ，秒t ，) 5 用i x y i 表示在x 中而不在y 中的l 的个数如果x 中分量是l 的行指标集包含于y 中分量是l 的行指标集，记作x l ， 定义1 1 1 3 【1 5 】设0 p 1 是一个实数，n 是有t 个分量的随机行向量，且其中每个 分量为l 的概率为p 给定一个n t 的( o ，1 ) 一矩阵q ，如下定义( m + n ) t 的矩阵 q ( m ，p ，亡) ：在q 的行上增加m 个随机行n ( 1 i m ) 用( 1 歹sn ) 表示q 的第j 行， 用u 1 ( 歹) ，u 掣u ) ，u ( 歹) ( 1 j n ) 表示q 的列，用u 1 ( i ) ，乱口( i ) ，u t ( i ) ( 1 i n + m ) 表示q ( m ，p ，亡) 的列 定义1 1 1 4 【1 5 】给定一个佗亡的( 0 ，1 ) 一矩阵q ，如下定义m 竹t 的( o ，1 ) 一矩阵 q + ( m ，p ，t ) ：其行由q ( m ，p ，亡) 的行n 和屿( 1 i m ，1 歹n ) 作交后得到，并且将 n 八按字典顺序排列我们用u l ( ，歹) ，( i ，歹) ，牡t ( i ，j ) ( 1 i m ，l 歹n ) 表示它的列 定义1 1 1 5 f 1 6 】设s l ，& ，& 是q 的列集，并且i s i 七( 1 z d ) 令z o 同， 称q ( m ，p ，t ) 的随机部分把& 。从s l 一，昌，鼠中分离出来，如果存在q ( m ，p ，亡) 的某 个随机行n ( i 【m 】) 使得q ( m ，p ，t ) 中& 。的每列在行n 都是l 。而对每个岛( z o z ) 都至 少存在一列在行n 为o 定义1 1 1 6 【1 5 l 设a 是仃t 的( o ，1 ) 一矩阵，令 n ( i ) k = 1 ，2 ，n ，u = 1 ，2 ，t 是a 的列设事件e 为“从t 列中任取七列 “。( i ) ) ：l ，对于任意一列( i ) g 8 口。( t ) ：l ， 有n ”( i ) v 笔l 口口( t ) ”设o e 这与互，噩：的选取矛盾因此只存 在唯一的满足条件的七一集，记为正假设正不是。，则日( 八五，阢( 歹) ) + h ( d f ( j ) ，鼽( 歹) ) 胃( 八正，d o ) ) = 日( 八互，八& 。) 2 e + 1 又由于日( d t u ) ，a ( 歹) ) e ，则日( 八正，鼽0 ) ) e + 1 这与正的选取矛盾则在q 中，正= & o 因此，断言成立 8 n ( 3 ，0 6 ，4 )t 上l ( 1 ，歹)t 1 2 ( i ，歹)t 3 ( i ，j )t 4 ( i ，j ) r 1 u l 0l10 r l u 2 oll 0 r i 蛐 0 1 1o r 1 龇 lo10 r 1 u 5 101o r 1 咄 1010 r l u 7 l1 0o r l 蛐 1l 00 r l u 9 1l00 r l u l o 1ll0 r l u 1 1 ll10 r i u 1 2 11l0 r 2 u l 0011 r 2 忱 0 oll r 2 u 3 0011 r 2 蛐 l0l1 r 2 u 5 l0l1 r 2 1011 r 2 u 7 l0ol r 2 嘶 l0o1 r 2 u 9 lo01 ，2 u l o 1010 r 2 u l l l0l0 r 2 u 1 2 10l0 r 3 u l 0lll r 3 u 2 o111 r 3 u 3 0lll r 3 u 4 0011 r 3 u 5 0011 r 3 u 6 00l1 r 3 u 7 01 o1 n u 80 1 ol r 3 u 9 o lo l r ： o “l 01l0 n o l i 01l0 ， i ? ( ) l 1 0 ( 图3 ) q 是( 3 ；3 ) 一分离i f ；1 ：的补阵( 图i ) ，按照定义1 1 1 3 对【2 加上3 个随机i i 后得 3 关于q a l m o s t 七e d i 鲥u n c 矩阵 3 1 当试验结果中错误的个数吲时 定义1 1 1 6 给出了q a l m o s t 后一出巧u 竹以矩阵的概念为了研究可容错的也s j u 佗以 矩阵的性质，我们有如下定义 定义3 1 1 设a 是佗亡的( o ，1 ) 一矩阵，令 ( i ) k = 1 ，2 ，礼，u = 1 ，2 ，t ) 是 a 的列设事件e 为“从t 列中任取七列 o ( i ) k 。，对于任意一列o ”( i ) g n 。( i ) ) k 。，至 少存在e + 1 个1 在n ( ) 中而不在v ：ln 。( i ) 中”设o k 1 ，对于任意一列u 钉( i ) g u 。( i ) ) 七- l ， 至少存在e + 1 个1 在八七一1 也( i ) 中而不在u 口( i ) 中的概率至少是q 证明由定义1 1 4 和定义3 1 1 直接可得 口 用命题1 2 2 的方法构作实验设d ( i ，歹) 为理想的试验结果，其中1 i m ，1 j 他当i 固定时d ( i ，j i ) 的子向量记作d i ( 歹) 设p ( i ，歹) 为有错的测试结果，其中1 i m ，l 歹扎当i 固定时护( i ，j ) 的子向量记作p i ( j ) 算法3 1 3 设r = s l 一，& ，鼠 为阳性七l 一复形集。其中七l 七对每个 i ( i 【仇】) ，设日( q ( j ) ，积( 歹) ) 【j 考虑q ( m ，p ，) 的列的集合耳= u u ( i ，歹) ：慨( 歹) 一 让v d ) i 【；j ，其中i 是固定的，u ( 歹) 是q 的列) 然后对满足i 耳i k 条件的耳进行检测， 以确定它是否是阳性复形 证明由于q 是n a l m o s t 七。一出s 歹n 礼d 矩阵的补阵，则对七l 七，由注记1 1 9 知q 必然至少是q a l m o s t 七：一饿s j 儿n c z 矩阵的补阵那么从q 的列中任取七i 列 u 。，( i ) 垒l ， 对于任意一列t ( i ) g u 。：( i ) ) 垒l ，至少存在e + 1 个l 在八竺l 舢( i ) 中，而不在u ( i ) 中的 概率至少是a 如果乜= 1 ，并且存在q ( m ，p ，) 的随机行n 把& 。( f o 【d 】) 从s l 一，s ，鼠 中分离出来此时在”( 小，p ，) 的n q 部分，由定义1 1 1 5 和q ( m ，p ，f ) 的定义可 知，q ( 仇，p ，z ) 中的鼠的各列与【2 中的瓯的各列是对应相等的再由命题1 2 3 可知，在 这部分，八鼠：d 。( n 那么! 与h ( 似( j ) ，胁( j ) ) s 【j 时，断言耳= & 。 事实上，( i ) 先证r ，：+ 在q ( m ，p ，) 中咖( ，) ，对应的在q 中有扎u ( j ) 瓯由，：八一n ( 儿 1 2 证明由推论3 1 4 可知，如果q ( m ，p ，) 的随机部分把鼠( z o 问) 从s l ，最， ，& 中分离出来，则通过算法3 1 3 ，可以把。检测出来的概率至少是a 再由命题 1 2 5 可知，q ( m ，p ，) 的随机部分把& 。( f o d 】) 从s l i 一，s ，中分离出来的概率是 西( z o ，d ，p ) 因此，通过算法3 1 3 ，可以把& 。检测出来的概率至少是q 垂( f 0 ，d ，p ) 这样检 测出某个阳性七l 一复形& 的概率至少是q 西( z ，d ，p ) 由期望的可加性可知，把阳性复形 都检测出来的期望至少是n 冬l 圣( z ，d ，p ) 口 3 2 当试验结果中错误的个数e 时 引理3 2 1 令1 冬d 【；j 即有d ；( 歹) 阢( 歹) 由于耳中的列除了全。列以外与q 中的列对应相等再由三角不等式，引理 3 2 1 和日( d i 0 ) ，阢d ) ) p 可知，日( 八日，阢0 ) ) h ( 八耳，八& 。) 一日( 八s ， ( j ) ) = 日( 八曰，八s 。) 一日( 仍( ? ) p ，( 川p + 1 一e = 1 这与八耳= 仇( 歹) 矛盾因此， q ( j ) = 胁( 歹) 口 算法3 2 3 设r = s 1 一s ，鼠l 为阳性七1 一复形集，其中知l “时每个 l ( i 【m 】) ，设h ( o 。( n ，( 川三r 在2 的列中找七l 一集正。，正：，z 。( 1 曼，乏j 使 1 4 4 关于复形的i n 肮坑幼模型 4 1 无错的情形 假设s 为n 个对象的集合设阳性尼1 一复形的个数为p ，i 佗 i 阮t d r 的个数为q ，且已知 p d ，口r ( r 为正整数) ，但是并不知道是哪种i n 肮硫卯模型这里的p 0 0 1 i n g 设计用关联 矩阵m 来表示m 的行由试验标定，列由所有被测对象标定m ，= 1 ，如果第j 个被测对象 包含在第 个试验中在不考虑i 礼托抚亡o r 的情况下，某个试验结果是阳性的当且仅当这个 试验包含某个阳性七l 一复形 定义1 1 2 l 给出了孤立行的概念为了研究关于复形的p o o l i n g 设计，我们有如下定 义7 定义4 1 1 在一个( o ，1 ) 一矩阵中，如果某一行只有七1 个l ，其中七l 七那么把这一 行叫做关于七l 的孤立行 引理4 1 2 如果一个( 七，d + r ) 一叠加码对应的矩阵m 有一个关于七1 的孤立行，则删 去这个行连同这七1 个l 所在的列，得到的矩阵仍然满足( 七，d + r ) 一叠加码的条件 证明利用( 七，d + r ) 一叠加码的定义可直接得到 口 下面考虑矩阵不包含关于七1 的孤立行的情形 引理4 1 3 在一个( 七，d + z ) 一叠加码对应的矩阵中，对任取的七l + d 列，至少有z + 1 行在七i 列的交中为l ，而在其它d 列的并中为o 证明由( 七，d + z ) 一叠加码的定义可知，它对应的矩阵是可以不含关于七l 的孤立行 的由注记1 1 2 0 可知，( 尼，d + z ) 一叠加码必然是( 七1 d + z ) 一叠加码下面用反证法证明 假设存在1 个七1 列集c 和d 列集d ，使得最多有z 行在c 的列的交中为l ，而在d 的 列的并中为o 由于矩阵没有关于后1 的孤立行，这? 行的l 必然被最多z 个其它列所覆盖 这样七l 列集c 的交被最多d + z 列的并所覆盖这与( 七l ，d + z ) 一叠加码所满足的条件矛 盾因此，结论成立 口 定理4 1 4 用( 七，d + r ) 一叠加码对应的矩阵可以把p 个阳性七l 一复形检测出来 证明设p 是一个阳性七l 一复形n 是一个阴性“一集令( c ) 为- 个七l 一集c 出现 f 这里的“出现”指某行在c 的七，列处都为1 ) 的附陀试验的个数对一个给定的r 集r ， f ”( c ) 为七l 一集c 出现且r 中没有l 的阴性i l i i ：验的个数定义 ( ( ) = i | l i ， r 。 定义1 1 2 3 给出了( d + ( m 伽d ，) ) e d i s j u n c t 矩阵的概念为了研究在m i n i 统卯 模型中检测阳性复形的可容错的p o o l i n g 设计，我们有如下定义 定义4 3 3 称m 为( s ，f + ( 仇伽td ，r ) ) 。一自由覆盖族对应的矩阵( m r ) ，如果它满 足对任取的两两不交的列集s ，厶冗，i s i s ，i 二i f ，l 兄l = r 至少存在e + l 行，在s 的交 中为l ，而在l 的并中为o ，在r 中至少有m 列的并为o 推论4 3 4 设m r 2 m 一1 ，在试验结果有最多e 个错误的m i 犯肮觇d 7 模型中， 用( s ，z + ( m 铡d ，) ) 勉一自由覆盖族对应的矩阵可以把p 个阳性七l 一复形检测出来 证明与定理4 2 1 的证明( i i ) 类似 结论 本文给出了一些关于复形的p o o l i n g 设计，并设计了一些算法，这对研究试验中阳性 复形的识别问题是非常重要的未来可以考虑的问题有： ( 1 ) 用不同的方法构作p 0 0 l i