一个Nphard问题,我都快把头想破了也没有想出来。(200分)

  • 主题发起人 主题发起人 qiaohj
  • 开始时间 开始时间
Q

qiaohj

Unregistered / Unconfirmed
GUEST, unregistred user!
一个Nphard问题,我都快把头想破了也没有想出来。(
描述:一个很长的字符串(由ATGC四个字母组成)的6-8个拷贝,将每一个字符串随机断成若干个子串(每一个字符串断开的位置、数目都不固定),将得到的所有的子串存放在一个数组中,然后将数组的顺序打乱,算法要求将该字符串恢复成原来的顺序
备注:
1、不知道原来字符串的长度
2、每一个子字符串和原来的字符串都有方向性,不会反接
要求:
1、时间复杂度和空间复杂度都不做具体要求,只要能保证恢复成原来的字符串就可以
我不知道说明白了没有,总之我是一点思路也没有。
 
没有人回答吗?
 
哈哈!大哥,您是不是在做人类基因测序呀? :)
有趣的问题...
一些需要了解的东西:
字符串的长度范围(10,100,1000,...)?
您的意思是不是有6-8个完全相同的字符串,分别被随机打断成若干截,最后混合到同一个
数组中去?
每个字符串被打散后生成的片段数?
字符串片断的长度范围?
最后,如果可以的话,请您给出一组测试数据(当然,如果实际的数据太长的话,您可以把
问题的规模适当的缩小(比如:长度约为实际应用的1/3,原字符串数量由6-8降为3-4))。
 
好像没有解呀
 
没错,是基因测序
字符串的长度范围(10,100,1000,...)?
答:不确定,200-300万,但很不确定
每个字符串被打散后生成的片段数?
字符串片断的长度范围?
答:不确定,500-1000个/条
测试数据太长了,最少的一个用文本文件表示是10M大的一个文件。
 
这恐怕是我到目前为止遇到的最复杂的算法问题了——极具挑战性呀!
这个问题是有解的,大不了在巧合的情况下,会有多个合理解——只不过,如果算法不是
极为优秀,很可能让深蓝算上100年也不会有结果(当然,考虑到本问题实际应用的数据量,
很可能任何算法都无法在100年内得到结果)。
我先说一说我对这个问题的理解:
1.统计得到片断的总长度 TotalLen
2.看 TotalLen 能被6-8中的哪几个数整除,进而得到原字符串的可能长度 PossibleLen[]
3.将片断的长度置于一个数组,将其看成一个正整数集合,然后考察这个集合,看能否从中
取出至少一个子集,使得该子集的元素之和和一个PossibleLen相等,进而过滤PossibleLen
数组。
4.对片段进行索引化处理——考虑到每个字符有4种可能,即2Bits,而一个字节有8Bits,
我们可以以4的整数倍的长度(比如:8-——不能太短,否则重复太多,索引就没有意义了;
也不能太长,否则整个内存一个索引都放不下)作为基本的索引元素。
我大致计算了一下,如果单个字符串长度在2*10^6(即2^21)左右,字符串片段的平均
长度为500(即2^9)左右,又认为共有8个相同的原始字符串,那么——总片断数应该在2^
(21+3-9)=2^15个左右。如果我们采用8个连续的字符作为索引的基本元素,那么索引的数量
为4^8,即2^16——我们基本上可以保证索引的唯一性(除非两个片段有重合的部分)。
5.下面就是算法的核心部分:
根据索引表,我们可以统计得到哪些片断有重合部分,并且可以根据索引重合的数量挑选
出最“可疑”的若干组片断,对它们进行字符串比较。首先,我们可以比较容易的找到位于
原始字符串两头的部分片段(因为它们的开始(结尾)部分都相同,没有错位),然后,就
互相依赖,不断的从两边道中间生成剩余的部分。
——讲了半天,好像只要第4,5步就可以了,等我试一试...(小时?天?月?)
 
creation-zy:
我在解释的具体一点儿:
事实是,由于DNA的特殊性,一次不能整条DNA的顺序都测出来。而且,确实不知道DNA究竟由200,000,000个碱基对还是有200,000,001个碱基对组成,只能估计是大约200万-300万,还往往不准;切断以后我只是知道切成了若干个片断,我也真的不知道究竟是切成了1000个还是1001个,每一个有多长?有可能有1个碱基,也有可能有2000个碱基,但是我只能最多测出前500-1000个,但是究竟是500个还是1000个,天知道。
就这样,用现有的数据,恢复成原来的DNA序列。
 
to creation-zy:
TotalLen 能被6-8中的哪几个数整除,进而得到原字符串的可能长度 PossibleLen[]
因为数据统统是不准确的,所以这个方法可能不太可行。(因为肯定不能精确到“个”)
另外,并不要求精确匹配,字符串模糊匹配就行了,保证匹配率在95%以上就行
 
哇!听了你的解释,我好像从还差一步登上山颠立刻又滑落到谷底——而且比初始状态还要
差...
核心问题:
能否做到没有一个DNA片断漏网?如果不能,请说明哪些类型的片断容易漏网,概率?
能否做到准确无误的检测每一个片断的长度及其ATGC的排列?如果不能,请给出偏差概率
(无不明白您在上面提到的“最多测出前500-1000个”中的“前”是什么意思?——比如有
一个实际长度为837的片断,你们可能只能测出其中头部600来个的ATGC序列?)。
如果上面的问题的答案不是完美的,那么请您一定给出误差的概率(比如总共3万多个片段
中,平均可能丢失5-20个等等)
 
你可以这样理解,6-8条一样的绳子,断开以后,混在一块儿。假设你能够恢复,就是下面这个样子。
---- ----- ---------- -------- --------- --------
-- ----- ----- ---------- ----- -------- ---- -----
……
--- ----- -------- -------- ------- ------- --------
原始DNA序列
------------------------------------------------------
但是我能保证100%的序列信息在片断中都会出现。
 
>>100%的序列信息在片断中都会出现
这个没有疑问。关键是——既然信息都在,您为什么又说“数据统统是不准确的”——精确
的测量每一个片段,然后求和即可,“不准确”从何而来呢?我关心的是——可以对哪些类型
的片段进行精确的测量,误差的概率是多大。比如:现有6条一样(或者说95%以上一样)的
DNA(长度均为2000000左右),现在将它们断裂成长度范围主要在500-1000的若干个片段,您
能否精确的得到每个片段的长度以及序列信息?——如果不能——概率呢?
还有,您说的“模糊匹配”也是一个大问题:
1.ATCTAGGCAT 2.ATCTAGCAT 3.ACCTAGGCAA
其中的1和2、3中的哪一个更相似?(我希望是3,如果是2的话,算法的复杂度将以几何级数
增长)
 
我想现在可以抛开一些细枝末节的地方,就看作是完全准确的。不用模糊匹配。
>>能否精确的得到每个片段的长度以及序列信息
能够得到的都看作是精确的,但是我不能知道我是不是得到了这个片段的所有信息(因为如果片段很长的话,我不能得到后面的若干信息。这个长度受到很多因素的影响,比如说实验时候的的温度,酶活性等等,所以,我能保证测出来的都是正确的,但是我不能保证也不知道子串我是不是已经将全部的测出来,有可能后面漏掉了一定的长度,但是有多长,不知道)
 
至于概率,由于不知道原始的DNA长度,所以没有办法算得出来。原来也有人估计,但是往往会得出令人啼笑皆非的结果,所以现在大家都放弃了这方面了。
 
Working...
生成100K的原始DNA,6个相同的DNA随机断裂成长度在1..1000之间的1235个片断。然后进行
“丢失片断信息”操作——假设我们可以随机的获得位于DNA片段头部的500..1000个序列信息
(也就是说长度小于等于500的片断信息必然是完整的)——结果共丢失213272个信息,约占
总信息量(6*100K)的34.7%。——足够逼真吗?

ps:提前帖子只要按“附加功能”中的“将此问题提前”即可,不用发贴。
 
结果共丢失213272个信息,约占总信息量(6*100K)的34.7%.
不能这样说,因为第一条链丢失的信息在第二条链中可能会找到,所以,在6-8条链切成的片断中,我可以保证所有的DNA遗传信息是完整的。
不知道我说明白没有,待会儿我看看能不能找到下载数据的网站,贴两条数据,你可以看看数据是什么样子的。
 
>>第一条链丢失的信息在第二条链中可能会找到
>>在6-8条链切成的片断中,我可以保证所有的DNA遗传信息是完整的
保证完整!?我有点喜出望外了 :)
但是,数据丢失是客观存在的,如果平均每个单个信息(注意,不是指整个片断)被丢失
的概率为30%,那么,某个信息被6个DNA都丢失的概率就是:0.3^6=0.000729,对于一个长度
约为2000000的DNA来说,就会有约1500个信息被漏检。假如丢失概率还算准确的话,只有当
原始DNA的数量大于12的时候,我们才能认为信息很可能是完整的。
还有,我上面说的“长度小于某一下限的片断,我们必定能够完整的测序”,实际上也是
这样吗?
 
>>被丢失的概率为30%
这种说法不准确,因为再DNA的切片中1-1000的概率是不一样的,应该说大部分是在1000以下的,所以,每条DNA的丢失信息概率是在10%一下,那么按照你的观点,应该有6-8条就应该足以保证99%的信息完整性。
>>长度小于某一下限的片断,我们必定能够完整的测序”,实际上也是这样吗?
可以这样认为
 
附(一个片断的数据)
>gi|22535292|gb|BC029875.1| Mus musculus, Similar to serine/threonine kinase 25 (yeast), clone IMAGE:4527370, mRNA
GCGTTCCGGGAGACCGAATTGCGGTGTGAGCCGCCGTGGGGACTGCGAAGCGGGCCCGGAGTCCGAGATG
GAGCCGCCCGGAGGTGCTTGAGGCGAGCGGGCGGAGCGGCTGCGACGGACTGGTCACGTCAGCGGGGACA
TGGCTCACCTCCGGGGCTTCGCGCACCAGCATTCTCGTGTGGACCCAGAGGAACTCTTCACCAAGCTTGA
CCGCATTGGCAAAGGCTCATTTGGGGAGGTGTACAAGGGGATCGACAACCACACCAAGGAAGTGGTGGCC
ATCAAGATCATTGACTTGGAAGAGGCCGAGGATGAAATTGAGGACATCCAACAGGAGATCACTGTGCTCA
GCCAATGTGACAGTCCTTATATCACCCGCTACTTCGGCTCCTACCTGAAGAGCACCAAGCTGTGGATTAT
CATGGAGTACCTGGGTGGTGGCTCTGCACTGGACTTGCTGAAACCTGGTCCCCTGGAAGAGACCTATATT
GCCACCATCTTGCGGGAGATCCTGAAAGGCCTGGATTATCTGCACTCAGAGCGCAAGATCCACCGAGATA
TCAAAGGTCCTGCGGGGTGGGCTTGGATGCAGTTCTGCCCATGACCTAGAAAGAGATGGGCATGTGGAGC
CTAGTAGATTGTGGTGCCTGAGGGCATGGGATGTGGGGAACGCTTCTGCCACCTGGAAACTGGGGAATTG
GGGGGGGGGGGTTGTCCATTTTACTTTTTATCCCCATTTTTAATGGCCACACTGAGGGTAGAGCCTAGGG
----------------------------------------------------------------------
下载的网址我再找找
 
后退
顶部