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

Q

qiaohj

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-09-02

• #1

一个Nphard问题，我都快把头想破了也没有想出来。（
描述：一个很长的字符串（由ATGC四个字母组成）的6-8个拷贝，将每一个字符串随机断成若干个子串（每一个字符串断开的位置、数目都不固定），将得到的所有的子串存放在一个数组中，然后将数组的顺序打乱，算法要求将该字符串恢复成原来的顺序
备注：
1、不知道原来字符串的长度
2、每一个子字符串和原来的字符串都有方向性，不会反接
要求：
1、时间复杂度和空间复杂度都不做具体要求，只要能保证恢复成原来的字符串就可以
我不知道说明白了没有，总之我是一点思路也没有。

 

Q

qiaohj

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-09-02

• #2

^

 

Q

qiaohj

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-09-02

• #3

没有人回答吗？

 

C

creation-zy

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-09-03

• #4

哈哈！大哥，您是不是在做人类基因测序呀？
有趣的问题...
一些需要了解的东西：
字符串的长度范围（10,100,1000,...）？
您的意思是不是有6-8个完全相同的字符串，分别被随机打断成若干截，最后混合到同一个
数组中去？
每个字符串被打散后生成的片段数？
字符串片断的长度范围？
最后，如果可以的话，请您给出一组测试数据（当然，如果实际的数据太长的话，您可以把
问题的规模适当的缩小（比如：长度约为实际应用的1/3，原字符串数量由6-8降为3-4））。

 

R

robertcool

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-09-03

• #5

好像没有解呀

 

Q

qiaohj

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-09-03

• #6

没错，是基因测序
字符串的长度范围（10,100,1000,...）？
答：不确定，200-300万，但很不确定
每个字符串被打散后生成的片段数？
字符串片断的长度范围？
答：不确定，500-1000个/条
测试数据太长了，最少的一个用文本文件表示是10M大的一个文件。

 

C

creation-zy

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-09-03

• #7

这恐怕是我到目前为止遇到的最复杂的算法问题了——极具挑战性呀！
这个问题是有解的，大不了在巧合的情况下，会有多个合理解——只不过，如果算法不是
极为优秀，很可能让深蓝算上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步就可以了，等我试一试...（小时？天？月？）

 

Q

qiaohj

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-09-03

• #8

creation-zy:
我在解释的具体一点儿：
事实是，由于DNA的特殊性，一次不能整条DNA的顺序都测出来。而且，确实不知道DNA究竟由200，000，000个碱基对还是有200，000，001个碱基对组成，只能估计是大约200万-300万，还往往不准；切断以后我只是知道切成了若干个片断，我也真的不知道究竟是切成了1000个还是1001个，每一个有多长？有可能有1个碱基，也有可能有2000个碱基，但是我只能最多测出前500-1000个，但是究竟是500个还是1000个，天知道。
就这样，用现有的数据，恢复成原来的DNA序列。

 

Q

qiaohj

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-09-03

• #9

to creation-zy:
TotalLen 能被6-8中的哪几个数整除，进而得到原字符串的可能长度 PossibleLen[]
因为数据统统是不准确的，所以这个方法可能不太可行。(因为肯定不能精确到“个”)
另外，并不要求精确匹配，字符串模糊匹配就行了，保证匹配率在95%以上就行

 

C

creation-zy

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-09-03

• #10

哇！听了你的解释，我好像从还差一步登上山颠立刻又滑落到谷底——而且比初始状态还要
差...
核心问题：
能否做到没有一个DNA片断漏网？如果不能，请说明哪些类型的片断容易漏网，概率？
能否做到准确无误的检测每一个片断的长度及其ATGC的排列？如果不能，请给出偏差概率
（无不明白您在上面提到的“最多测出前500-1000个”中的“前”是什么意思？——比如有
一个实际长度为837的片断，你们可能只能测出其中头部600来个的ATGC序列？）。
如果上面的问题的答案不是完美的，那么请您一定给出误差的概率（比如总共3万多个片段
中，平均可能丢失5-20个等等）

 

Q

qiaohj

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-09-03

• #11

你可以这样理解，6-8条一样的绳子，断开以后，混在一块儿。假设你能够恢复，就是下面这个样子。
---- ----- ---------- -------- --------- --------
-- ----- ----- ---------- ----- -------- ---- -----
……
--- ----- -------- -------- ------- ------- --------
原始DNA序列
------------------------------------------------------
但是我能保证100%的序列信息在片断中都会出现。

 

C

creation-zy

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-09-03

• #12

>>100%的序列信息在片断中都会出现
这个没有疑问。关键是——既然信息都在，您为什么又说“数据统统是不准确的”——精确
的测量每一个片段，然后求和即可，“不准确”从何而来呢？我关心的是——可以对哪些类型
的片段进行精确的测量，误差的概率是多大。比如：现有6条一样（或者说95%以上一样）的
DNA（长度均为2000000左右），现在将它们断裂成长度范围主要在500-1000的若干个片段，您
能否精确的得到每个片段的长度以及序列信息？——如果不能——概率呢？
还有，您说的“模糊匹配”也是一个大问题：
1.ATCTAGGCAT 2.ATCTAGCAT 3.ACCTAGGCAA
其中的1和2、3中的哪一个更相似？（我希望是3，如果是2的话，算法的复杂度将以几何级数
增长）

 

Q

qiaohj

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-09-03

• #13

我想现在可以抛开一些细枝末节的地方，就看作是完全准确的。不用模糊匹配。
>>能否精确的得到每个片段的长度以及序列信息
能够得到的都看作是精确的，但是我不能知道我是不是得到了这个片段的所有信息（因为如果片段很长的话，我不能得到后面的若干信息。这个长度受到很多因素的影响，比如说实验时候的的温度，酶活性等等，所以，我能保证测出来的都是正确的，但是我不能保证也不知道子串我是不是已经将全部的测出来，有可能后面漏掉了一定的长度，但是有多长，不知道）

 

Q

qiaohj

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-09-03

• #14

至于概率，由于不知道原始的DNA长度，所以没有办法算得出来。原来也有人估计，但是往往会得出令人啼笑皆非的结果，所以现在大家都放弃了这方面了。

 

Q

qiaohj

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-09-03

• #15

^

 

C

creation-zy

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-09-03

• #16

Working...
生成100K的原始DNA，6个相同的DNA随机断裂成长度在1..1000之间的1235个片断。然后进行
“丢失片断信息”操作——假设我们可以随机的获得位于DNA片段头部的500..1000个序列信息
（也就是说长度小于等于500的片断信息必然是完整的）——结果共丢失213272个信息，约占
总信息量（6*100K）的34.7%。——足够逼真吗？

ps:提前帖子只要按“附加功能”中的“将此问题提前”即可，不用发贴。

 

Q

qiaohj

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-09-04

• #17

结果共丢失213272个信息，约占总信息量（6*100K）的34.7%.
不能这样说，因为第一条链丢失的信息在第二条链中可能会找到，所以，在6-8条链切成的片断中，我可以保证所有的DNA遗传信息是完整的。
不知道我说明白没有，待会儿我看看能不能找到下载数据的网站，贴两条数据，你可以看看数据是什么样子的。

 

C

creation-zy

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-09-04

• #18

>>第一条链丢失的信息在第二条链中可能会找到
>>在6-8条链切成的片断中，我可以保证所有的DNA遗传信息是完整的
保证完整！？我有点喜出望外了
但是，数据丢失是客观存在的，如果平均每个单个信息（注意，不是指整个片断）被丢失
的概率为30%，那么，某个信息被6个DNA都丢失的概率就是：0.3^6=0.000729，对于一个长度
约为2000000的DNA来说，就会有约1500个信息被漏检。假如丢失概率还算准确的话，只有当
原始DNA的数量大于12的时候，我们才能认为信息很可能是完整的。
还有，我上面说的“长度小于某一下限的片断，我们必定能够完整的测序”，实际上也是
这样吗？

 

Q

qiaohj

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-09-04

• #19

>>被丢失的概率为30%
这种说法不准确，因为再DNA的切片中1-1000的概率是不一样的，应该说大部分是在1000以下的，所以，每条DNA的丢失信息概率是在10%一下，那么按照你的观点，应该有6-8条就应该足以保证99%的信息完整性。
>>长度小于某一下限的片断，我们必定能够完整的测序”，实际上也是这样吗？
可以这样认为

 

Q

qiaohj

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-09-04

• #20

附（一个片断的数据）
>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
----------------------------------------------------------------------
下载的网址我再找找