辛空间的排列问题及具有容错能力的pooling设计的紧界

数学物理学报 ›› 2012, Vol. 32 ›› Issue (2): 414-423.

辛空间的排列问题及具有容错能力的pooling设计的紧界

赵向会¹|李莉²|张更生^2*

1.河北科技大学理学院河北石家庄 050018;
2.邢台学院教务处河北邢台 |054001;
3.河北师范大学数学与信息科学学院河北石家庄 |050016

收稿日期:2010-10-08 修回日期:2011-09-06 出版日期:2012-04-25 发布日期:2012-04-25
通讯作者: 张更生，gshzhang@hebtu.edu.cn E-mail:gshzhang@hebtu.edu.cn
基金资助:
河北省自然科学基金(A2009000253)资助

An Arrangement Problem of Subspaces of |Symplectic Space and Tighter |Bound of an Error-tolerant Pooling Design

ZHAO Xiang-Hui¹, LI Li², ZHANG Geng-Sheng^2*

1.Institute of Science, Hebei University of Science and Technology, Shijiazhuang 050018;
2.Office of Educational Administration, Xingtai University, Hebei Xingtai 054001;
3.Mathematics and Information Science College, Hebei Normal University, Shijiazhuang 050016

Received:2010-10-08 Revised:2011-09-06 Online:2012-04-25 Published:2012-04-25
Contact: ZHANG Geng-Sheng，gshzhang@hebtu.edu.cn E-mail:gshzhang@hebtu.edu.cn
Supported by:
河北省自然科学基金(A2009000253)资助

摘要/Abstract

摘要：

该文利用辛空间上的子空间构造了一类新的d ^z析取矩阵,然后研究了如下排列问题：对于给定的整数m, r, s, ν, d, q 和辛空间F^2ν _q中的一个(m, s) 型子空间S, 这里ν+s≥ m>r≥2s-1≥1, d≥2, q 是一个素数的幂, 作者从S中找到d个(m-1, s-1) 型子空间H₁, … H_d, 使包含在这些(m-1, s-1) 型子空间中的(r, s-1)型子空间个数达到最大. 然后利用这个排列的有关结论, 给出了一类pooling设计的紧界.

关键词: pooling 设计, d^z析取, 辛空间, 排列问题, 紧界

Abstract:

In this paper, we design a class of new d ^z-disjunct matrices with the subspaces of the symplectic space and study the following
arrangement problem. Given integers m, r, s, ν, d, q where ν ≥m≥r+2≥2s≥2, d≥2, q is a prime power, and a subspace S of type (m, s) of symplectic space F^2ν_q, we find d subspaces of type (m-1, s-1) H₁, … H_d of S that maximize the number of the subspaces of type (r, s-1) contained in at least some H_i(1\le i\le d). Then with obtained result, we give the tighter bound of pooling design.

Key words: Pooling design, d ^z-disjunct, Symplectic space, Arrangement problem, Tighter bounds

中图分类号:

05E15

赵向会, 李莉, 张更生. 辛空间的排列问题及具有容错能力的pooling设计的紧界[J]. 数学物理学报, 2012, 32(2): 414-423.

ZHAO Xiang-Hui, LI Li, ZHANG Geng-Sheng. An Arrangement Problem of Subspaces of |Symplectic Space and Tighter |Bound of an Error-tolerant Pooling Design[J]. Acta mathematica scientia,Series A, 2012, 32(2): 414-423.

参考文献

[1] Balding D J, Bruno W J, Knill E, Torney D C. A Comparative of Non-adaptive Pooling Design. Genetic Mapping and DNA Sequencing (Minneapolis, MN, 1994). New York: Springer, 1996: 133--154

[2] Du D Z, Hwang F K. Combinatorial Group Testing and Its Applications (2^nd ed). Singapore: World Scientific, 2000

[3] Du D Z, Hwang F K. Pooling Designs and Nonadaptive Group Testing: Important Tools for DNA Sequencing. Singapore: World Scientific, 2006

[4] D'yachkov A G, Hwang F K, Macula A J, et al. A construction of pooling designs with some happy surprises. Journal of Computational Biology, 2005, 12: 1129--1136

[5] Macula A J, Rykov V V, Yekhanin S. Trivial two-stage group testing for complexes using almost disjunct matrices. Discrete Applied Mathematics, 2004, 137: 97--107

[6] Balding D J, Torney D C. Optimal pooling design with error detection. Journal of Combinatorial Theory (Series A), 1996, 74: 131--140

[7] Macula A J. A simple construction of d-disjunct matrices with certain constant weights. Discrete Mathematics, 1996, 162: 311--312

[8] Macula A J. Error-correcting nonadaptive group testing with d^e-disjunct matrices. Discrete Applied Mathematics, 1997, 80: 217--222

[9] Knill E, Bruno W J, Torney D C. Non-adaptive group testing in the presence of error. Discrete Applied Mathematics. 1998, 88: 261--290

[10] Ngo H Q, Du D Z. New constructions of non-adaptive and error-tolerance pooling designs. Discrete Mathematics, 2002, 243: 161--170

[11] Huang Tayuan, Weng Chihwen. Pooling spaces and non-adaptive pooling designs. Discrete Mathematics, 2004, 282: 163--169

[12] Wu Weili, Huang Yaochun, Huang Xiao, Li Yingshu. On error-tolerant DNA screening. Discrete Applied Mathematics, 2006, 154: 1753--1758

[13] Ngo H Q. On a hyperplane arrangement problem and tighter analysis of an error-tolerant pooling design. Journal of Combinatorial Optimal, 2008, 15: 61--76

[14] Macula A J, Gal S, Andam C, Bishop M A, Renz T E. Pcr Nonadaptive group testing of DNA libraries for biomolecular computing and taggant applications. Discrete Mathematics, Algorithms and Applications, 2009, 1: 59--69

[15] Lang W, Wang Y, Yu J, et al. Error-tolerant trivial two-stage group testing for complexes using almost separable and almost
disjunct matrices. Discrete Mathematics, Algorithms and Applications, 2009, 2: 235--251

[16] Wan Zhexian. Geometry of Classical Groups Over Finite Fields (2^nd ed). Beijing: Science Press, 2002

[17] D'yachkov A G, Macula A J, Rykov V V. New constructions of superimposed codes. IEEE Transactions on Information Theory, 2000, 46: 284--290

[18] D'yachkov A G, Macula A J, Rykov V V. New Applications and Results of Superimposed Code Theory Arising from the Potentialities of Molecular Biology. Numbers, Information and Complexity. Dordrecht: Kluwer Academic Publishers, 2000

[19] D'yachkov A G, Rykov V V. Optimal superimposed codes and designs for Renyi's search model. Journal of Statistical Planning and Inference, 2002, 100: 281--302