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

来吧。

很遗憾，这回到北京没空出来玩（在远郊，每天课程都排得满满的 ）。
今天刚刚发现算法中的一个错误——片断偏移量的符号弄反了，纠正之后，在没有误差的
情况下，初步匹配形成的大片断数从100-200锐减至不到20：
初步片断拼接消耗时间：3.17 秒
[初步片断拼接信息]
可拼接片断数=8739
最小匹配对数=6
稀疏索引间隔=5
被成功拼接的片断数=8739
成功拼接片断比率=100.00%
最小吻合比率=95%
拼接过程中的无效匹配数=0
拼接后形成大片断数=15
大片断中的的片断总数=14607
平均每个大片断中的片断数=973.80
拼接片断消耗时间：0.00 秒

我现在对算法的原理进行形象化的描述：
现有两个DNA片断A、B。通过对它们进行索引分析，我们发现它们有超过100个索引是相同
的，可以对它们进行进一步的片段匹配分析。
分析过程中，我们发现在它们的索引交集之中，有十几个索引在A,B中的分部的相对位置
都是一致的：
索引 在A中的位置 在B中的位置
[CATCTTCCATC] 50 320
[TAACGATCTGA] 58 328
[TGTCCTGTTTT] 459 729
[CATCTTCCATC] 124 394
[CCCTTGATTCG] 781 1051
... ... ...
由于匹配对数已经达到索引的最小匹配对数，我们可以初步认为B相对于A的偏移量为:50-
320=-270。
为了进一步确认，最大限度的消除误差的影响，我们对这两个片断的重合部分进行匹配统
计，发现两个片断总共854个位置重叠的元素中，共有847个元素是相同的，已经达到了95%
以上的可信匹配比率。
经过这几道关卡，我们完全可以认为，DNA片断A,B有重合的部分，并且B相对于A的偏移量
是-270。
以上面的匹配算法为基础，我们可以通过一个种子片断，通过匹配连结，最终获得由成百
上千个片断组成的大片断。
正在处理最后的大片断的连接部分。(出差期间没有写程序，耽误了一些时间，见谅!)

急需要可操作的完整的实验数据。
完整的程序（含源代码）在我的主页有下载：
http://www24.brinkster.com/creationzy/myprg.htm
不断更新中。

你的sina信箱不能收信了，在这里和你联系把。
你要的数据我会尽快给你找到。
另外，你能完整的描述一下你的算法吗？
我看你的源码注释很少，加上我本身不是学计算机的，算法底子很浅，看起来比较费劲

已经完稿，请到我的主页去下载程序及源代码。
在误差小于等于1%的时候效果很好，一旦误差超过4%...
最小吻合比率应该视数据误差而定，一般为 100%-2.5*误差。
我发现一次性完全拼接似乎是多余的，因此没有实现。在实际操作时，可以在初步拼接之后
用“从文件读取”，选择上一次生成的最终DNA文件（默认为 Final.txt）即可将上一次的结
果作为原始数据，进行再次拼接。（注意到每次拼接之后片段的平均长度都会变大，为了提高
效率，每次都应该增大“最小索引匹配对数”和“稀疏索引间隔”的值）。

几个问题：
1、该算法的复杂度多少？也可以说再多大的数量级上（原始序列的长度），完成最终的拼接工作所需的总共时间是多少？能不能给个大概的估计值。

2、你的主页上面没有源程序啊？
3、能不能具体的讲一讲你的建索引的过程和"得到每个索引在片断中的偏移量，这样形成两个数组"的过程（我想我还是先看看程序再说吧，我没有下载到你的程序）
谢谢你了，有时间一定请客。
有什么我能帮上忙的，讲话就行！

现在特别想拿到源程序好好看一看。有一点儿像吸毒的人想吗啡的感觉。
其实这个东西是给mm写的，他们在做这方面的工作，进展不是很顺利。我的任务是将你的算法用c来实现，然后在Linux下面运行通过，我不知道自己能不能完成。
自己在学习GIS的二次开发，JAVA的，进展不顺利，资料太少。
另外，你有关于后缀树的资料吗？最好是中文的，其中的一个部分要用到后缀树的算法。
最后，你做的东西中好像没有考虑到DNA中的重复序列的问题，DNA不是完全随机的，它有很多的重复序列，这样会影响到最终的拼接结果。现在正在解决的问题就是如何标记出重复序列，大家讨论的结果就是用后缀树的数据结构来完成，能不能给点你认为的思路？

再次感谢。

我好像也学过数据结构，怎么就压根没听说过“后缀树”？失败呀。
老大，我的程序完全可以用Kylix3在Linux下编译的，我昨天刚试过的，不用翻译。（只不过
运行速度好像还不到Windows的1/20——不懂呀）
我的算法有进度条显示的，你准备好1G以上的CPU，500M以上的内存，再加上些许的耐心即可。
主页现在好像有些问题...

后缀树:suffix tree。www.google.com上面英文的资料很多，用来做字符串匹配的。不过看得不是太明白。
翻译成纯C是为了将程序并行处理，也许曙光的服务器对Kylix编译的东西支持不好吧？谁知道呢，反正人家的要求是用纯C
我的CPU是1.4的，内存小了点儿，256的，不过是Rambus的。
能把源程序发给我一份吗？

多谢乔兄！
我下载了一分资料，看了几页，好像这种算法是用于精确匹配的，不适合您提出的不精确
匹配的情况。
我用你给出的实验数据进行了匹配试验，其中有一个结果是：两个长度均在1000上下的片
断A、B，我的匹配算法发现B相对A的偏移量为200多。然后，我将A截断200多以后，和B分别
存入两个文件，用我的工具对两个文件进行XOR操作，发现：这两个文件的头、尾均有约数
十字节的异或值不为零，而中部的近800个字节中，只有两个零星的XOR值不为0。像这样的
数据，我认为只能依靠模糊匹配，而我的基于索引匹配的算法是完全可以做到的。
当然，我现在的算法虽然基本上实现了模糊匹配的功能，但是它的时空复杂度还有待改进
——在最坏的情况下，拼接片断算法的时间复杂度为 O(AvgLen^2*n^3)，即片断的平均长度
的平方乘以片断数的三次方——太可怕了（生成索引及索引匹配的时间复杂度分别为O(n*
AvgLen*Log2(AvgLen))以及O(n*(每片断对应的索引数*每索引对应的片段数+n))）。由于精
力的关系，我目前还没有采用最复杂但效率最高的算法（可能将算法复杂度中的指数减掉2-
3！）。

并不是这样的，也可以进行模糊匹配的。要改变一下结构
我正在学习中，有了心得讨论一下。
这个我结了，还有什么发信给我好了。

接受答案了.