中文XML论坛--超级难题应该没人做得出

贴子主题：超级难题应该没人做得出

本主题类别:

二进制指纹向量丢失位计算
基因表达谱是一个二维实数数组[aij]n*m，用来表达生物探针与实际DNA片段的匹配情况。在癌症DNA诊断与DNA克隆分类应用中，必须将基因表达谱进行数据分类。
基因表达谱分类实际是基因表达数据向量的分类，分类原则为：将[aij]n*m看作m个n维实数向量，若两个向量十分类似，即可归为一类。可将基因表达谱转化为n位二进制序列集合F={X1,…,Xm}{0,1}n，“能够转化为相同二进制序列的实数向量归为同一类”。但在实数向量到二进制序列的转化中，某些二进制位难以确定其0/1取值，这样的二进制位称为丢失位。转化得到的可能带有丢失位的二进制向量又称为指纹向量。不含有丢失位的指纹向量称为结果向量。
必须确定指纹向量中丢失位的0/1取值，才能完全确定基因表达谱的分类结果。丢失位确定后，有多少个结果向量，基因表达谱即分为几类，基因表达普分类可看作指纹向量分类，同类指纹向量可得到相同的结果向量。按照以往经验，结果向量越少，则分类结果越准确。因此可通过“结果向量最少”为目标计算指纹向量中丢失位取值。例如有指纹向量集F={X1=00N01, X2=N0101, X3=0N00N, X4=01N00}，其中N表示丢失位，最少可将X划分成两类，{X1,X2}一类，对应的实际结果向量为00101，{X3, X4}分为一类，对应的实际结果向量为01000。在实际应用中，指纹向量出现丢失位是必然的，但每个指纹向量中丢失位数不可能太多。因此问题如下：
(1)假设每个指纹向量中最多含有一个丢失位，试设计算法计算给定指纹向量中丢失位取值，使结果向量数最少。
(2)下面给出两组指纹向量。每个指纹向量均为20位，其中一位为丢失位。试用你的方法分别计算两组向量的丢失位，给出得到的结果向量。

由于题目数据过大,只给出一部分数据了

指纹向量集1
FPbegin
000N1111101010000100
000111111010100001N0
00011111101010N00100
00011111N01010000100
000111N1101010000100
由于题目数据过大,只给出一部分数据了,关键是方法嘛,请大家努力提供方法!


	W 3 C h i n a ( since 2003 ) 旗下站点苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》	46.875ms