爱吱声

标题: 字符串匹配 [打印本页]

作者: 喜欢喝冰茶 时间: 2013-10-7 04:13
标题: 字符串匹配
本帖最后由橡树村于 2013-10-15 15:48 编辑

字符串匹配，string match，这个是计算机里面常见的问题，例如：

string1: TACGGCATGGCTATCGTAGCTAG

string2: GCTAT

要求在string1里找到string2的位置，如果存在多个的话，都要找出来。

可以自己估计一下时间复杂度，真实的例子是，String1长达3billion，或者6个billion。string2长约一、二百，但是数目可以是以billion计的。

先扛着。

作者: 晨枫 时间: 2013-10-7 05:16
怎么感觉这个和基因研究有关？识别基因里的某种特征？

作者: MacArthur 时间: 2013-10-7 06:17

晨枫发表于 2013-10-6 16:16
1 B% g: e" k! G+ B( @% i. |2 x8 r怎么感觉这个和基因研究有关？识别基因里的某种特征？

这就是基因BLAST算法的标准定义嘛。。。

Google ＂Blast算法＂，一堆开源程序。

作者: 晨枫 时间: 2013-10-7 07:21

MacArthur 发表于 2013-10-6 16:17
& }" b! ~1 w% L6 [这就是基因BLAST算法的标准定义嘛。。。( B# i. U! R7 O, d$ V; a

+ `4 M, z8 q' I& oGoogle ＂Blast算法＂，一堆开源程序。

莫非麦帅也是干这一行的？不然怎么会这么熟悉？

作者: 假如十八 时间: 2013-10-7 07:28

晨枫发表于 2013-10-7 07:21
, i) F! l6 j; c$ a V莫非麦帅也是干这一行的？不然怎么会这么熟悉？

这都不用动手写吧？正则表达式很多语言都支持啊

作者: 晨枫 时间: 2013-10-7 07:29

假如十八发表于 2013-10-6 17:28
r P3 k9 g1 F* m这都不用动手写吧？正则表达式很多语言都支持啊

有可能是普通的bubble sort和quick sort之间的差别？也就是说，普通算法的效率不适合特别大的海量比较计算？

作者: 冰蚁 时间: 2013-10-7 07:33
老兵有个群组，软件人家。

作者: 巴巴爸爸 时间: 2013-10-7 08:38

MacArthur 发表于 2013-10-7 06:17
) K" y, v6 l2 r3 D, B1 |- r这就是基因BLAST算法的标准定义嘛。。。
% `% D8 _5 b3 E7 j4 ^; ^! Q: v
1 ~: f( }4 x* ]: V) y5 B7 a- y" D' FGoogle ＂Blast算法＂，一堆开源程序。

blast......恍若隔世，你不说我都忘了曾经有那么一段时间天天跟这个较劲。。。。

作者: 喜欢喝冰茶 时间: 2013-10-7 09:01
最野蛮也是最简单的办法：一个一个比。

string1: TACGGCATGGCTATCGTAGCTAG3 T; h6 }7 B& U: k
) T8 q' w" P, V: o
string2: GCTAT' ?( P$ n4 @5 `% s

/ f. ]* K0 g* b* Y要求在string1里找到string2的位置，如果存在多个的话，都要找出来。

拿string2和string1比，至少需要比string1的长度减去string2的长度再加1次。在实际应用中，如果string1的长度是10^9，而string2只有一二百，那么做一次基本上就是比10^9次。当然如果很幸运，string2在string1开始的地方，那一次就够了。所以平均来说，要比10^9／2次，也就是O(10^9)。

但是如果实际情况中，有10^6到10^9个string2s，那总共要比多少次？10^15到10^18次。这什么概念？不考虑所有的overhead，比一次只需一个时钟，那3G的CPU，意味着一秒可以比10^9次，要完成这样一个工作，需要10^6到10^9秒，1年＝365天 x 24小时 x 3600秒＝31Millon秒。也就是说，最短大约需要12天，最长需要30年。如果这样的操作做十次，一台CPU要算至少120天到300年！！！人都死几次还没比完，太郁闷了，所以不可接受。

那如果是这个样子

string1: AAAAAATTTTCCCCCGGGTTTTAAAACCCCCCGG
string2: TTAAA

是不是会快很多？

继续扛。

作者: qiuwen777 时间: 2013-10-7 09:47

喜欢喝冰茶发表于 2013-10-7 09:01
6 t+ X: _. n* H/ H最野蛮也是最简单的办法：一个一个比。

帮你顶一下。很多问题，看起来很简单，但是在数据量大的情况下，根本不是那么回事。
这可以产生很多计算机专家。
对于算法的问题，一般我都躲着。

作者: 喜欢喝冰茶 时间: 2013-10-7 10:35
本帖最后由喜欢喝冰茶于 2013-10-6 20:40 编辑

如果两个字符串是这个样子6 |; y5 A; F/ @

( B) N; l% g4 q- g0 zstring1: AAAAAATTTTCCCCCGGGTTTTAAAACCCCCCGG
# [+ b* I* C7 {0 d3 Ystring2: TTAAA

当然要省很多时间，因为不需要对string1一个一个比了！！！

string1可以写成：
长度字符起始位置
6    A    1
4    T    7
5    C    11
3    G    16
4    T    19
......

所以当用string2去比的时候，一开始根本就不用考虑字符为A，G，C的行，因为string2开始是T。因此在这个例子中，不需要去检查string1的每个位置，而是非常有限的几个位置，所以可以省很多时间。

那么如果存在一种这样的转换方法能够将主贴里的字符串转化成这种，势必会省很多时间。有这样一种方法吗？哪里去找？

如果你是有心人，你觉得这个东西最常用在哪里？

对了，文件压缩。

事实上，真正的解决方法就是借鉴了最早用于文件压缩的一种算法，称为Burrows－Wheeler Transform，又称block-sorting compression。这是当年在DEC工作的Michael Burrows和David Wheeler发明的，所以以他们的名字命名，bzip2的压缩文件就是基于该算法的。它的转换其实很简单，如果感兴趣大家可以google／wiki（wikipedia上很详细的操作细节）上去看细节，但简单的来说，就是把一个字符串头围相接，不停的移动一位，然后排序，最后取出最后一列就行了。Burrows－Wheeler Transform的特性就是转换后的字符串相对于原始字符串含有大量的重复字符片段，所以就可以使得我们的问题变的相对快捷。

那么是否就十全十美，万事大吉了呢？这个需要从实际的具体需求来看。

扛吧，没什么好说的。

作者: 喜欢喝冰茶 时间: 2013-10-7 10:38

MacArthur 发表于 2013-10-6 16:17
! x' x4 ~6 j( u" n6 q+ j这就是基因BLAST算法的标准定义嘛。。。
% K8 o, C9 J) l( [
$ v; O y$ ], z2 e; `, CGoogle ＂Blast算法＂，一堆开源程序。

blast并非只是解决基因的问题，蛋白同样适用，只不过相对于DNA／RNA而言，蛋白质要复杂得多。

作者: MacArthur 时间: 2013-10-7 11:35

喜欢喝冰茶发表于 2013-10-6 21:38
5 \/ |: l0 `# Rblast并非只是解决基因的问题，蛋白同样适用，只不过相对于DNA／RNA而言，蛋白质要复杂得多。 ...

不明觉厉。。。上Billion字节的操作，想想就头大。。。这个规模是不是得上并行计算了？

作者: 喜欢喝冰茶 时间: 2013-10-7 11:45

MacArthur 发表于 2013-10-6 21:35
9 N {' g# V, s x不明觉厉。。。上Billion字节的操作，想想就头大。。。这个规模是不是得上并行计算了？* |( ?4 U$ S- X, s0 V
...

blast好像支持吧，主要不是分布式的问题，而是blast使用的算法对蛋白的分数的定义是很有讲究的，这些分数的定义大概要涉及到另外一个和进化相关的计算领域。

作者: 老芒 时间: 2013-10-7 11:47
本帖最后由老芒于 2013-10-8 00:21 编辑

这样的短贴适合聊天版。

作者: martian 时间: 2013-10-7 12:27

喜欢喝冰茶发表于 2013-10-7 10:35
' c4 s+ a: n9 G0 Z% _4 \* R当然要省很多时间，因为不需要对string1一个一个比了！！！& a# Y+ r) O! L. F, t% o, R7 M
' I; c9 g! H% n) |9 q, [! l& \
string1可以写成：

是要找pattern

Ensembl就用了这种数据压缩方法，
AAATTCCGG
A3T2C2G2

把string1，分成若干片段，多进程查找。

作者: 喜欢喝冰茶 时间: 2013-10-7 21:57
本帖最后由喜欢喝冰茶于 2013-10-7 12:05 编辑

已经有同校指出了blast，一个用于对生物大分子的测序程序。这东西正式诞生于1990年，同年人类基因组计划启动。它不仅可以用于DNA/RNA的测序，还可以对蛋白测序。六年前在河里曾经写过一个搭积木的小玩意儿，其中涉及到利用计算方法来预测实验中很难测量的蛋白质空间结构，最有效的计算方法就是同源模型。在这个模型里面，我们允许寻找的字符串,string2可以不用严格的和string1，也就是模板序列，匹配的。换句话说，就是字符串匹配是容错的。具体到主贴里提到的真实问题的挑战，就是模板字符串是人类的基因组（genome），单链长达3billion结构单位，也就是3billion的字符长度，而DNA是双链的，也就是6B的长度。想一想，每个人都是unique的，所以即使都是“健康人”，每个人的基因组都不会完全一样，因此，这种字符串的匹配一定是允许错误的，否则的话，如果大家都一样，即使算法速度再慢都不是问题，因为只做一次，从时间复杂度上，就是0。

那么如果考虑容错的匹配，基于bwt方法的算法将面临一个巨大的挑战，因为BWT是严格转换的，可是容错的实际需要，就要考虑转换前和转换后的字符串的错误问题，这会使的问题非常复杂。因此，现在的解决方案就是，当我们需要更多的关注容错的问题时，我们仍然使用传统的，也就是blast所使用的Smith－Waterman算法。具体的细节，感兴趣的可以google／wiki，基本来讲，这是一种被称之为动态编程的计算机算法，可以很好的考虑容错问题，诸如substitution、insertion、deletion或者indel（也就是insertion和deletion的混合体），而这些“错误”，则广泛的存在于病人的基因组中，特别是癌症基因组。当然，现在所使用的smith－waterman基于的方法都是修改了的，主要是计算机算法上的加速，诸如hash的SW算法。

但是，bwt基于的方法，运算速度非常快。曾经有朋友几年前做过测试，拿上一代mac book pro，对于5万个长达100字符的输入string2s，string1是人类第一号染色体的DNA序列。blast要跑a couple of minutes，但是第一代bwt based的应用程序，在用手捋了一下头发之后，结果就出来了，当时朋友还以为自己错了。所以相对于blast所使用的算法而言，以bwt为基础的应用，诸如bowtie／bowtie2，bwa（short read version），soap（主要运行于HPC上，由位于深圳的华大基因开发，他们大概是曙光的最大用户），这些闻名遐迩的应用程序（从文章引用次数上，bowtie是最早的，发表于2009年，引用数已经接近3千，bwa大约2千五，soap约为700。引用它们的文章，不仅包括Nature，Science，Cell还有医学领域里的一些著名杂志，像新英格兰医学杂志），使得新型测量技术得以广泛的应用。如果不考虑监管、法律和伦理方面的问题，在可以预见的将来，你的mobile device里存储自己的DNA序列将不再是梦想而是现实，而人们同时希望，DNA序列的检测成为新生儿的常规检查。

作者: 喜欢喝冰茶 时间: 2013-10-9 10:43
本帖最后由喜欢喝冰茶于 2013-10-10 15:20 编辑

这个帖子里的东西，看起来似乎是一个简单的计算问题，但是却很可能是一场改变人类健康革命的基础。正是由于高速有效的匹配算法的发展，才使得新的测序技术得以广泛应用，不仅是基础研究，而更重要的是临床应用，这里简单的提到一些。等有空的时候，写一些有关基于genome和tanscriptome的技术以及实际应用，像分子诊断技术，这将对癌症的诊断和预期提供巨大的帮助。感兴趣的同学，可以看看AML，也就是急性骨髓性白血病的亚型分类标准，特别是WHO的新标准，还有预期，是否能看懂。

作者: chalet 时间: 2013-10-11 12:06

喜欢喝冰茶发表于 2013-10-9 10:43 * A2 ~$ [3 } O( C9 \% n) J
这个帖子里的东西，看起来似乎是一个简单的计算问题，但是却很可能是一场改变人类健康革命的基础。正是由于 ...

欢迎欢迎。

如果说硬要分类，这个应该还是属于生物信息学领域吧，在科教学圃应该很对口啊。

使用NCBI网站上的BLAST都是10多年前的事情了，一眨眼人都老了。。。

关于你下面会介绍的内容，非常期待。很久没有学习这方面的知识了，落伍了，亟待补课

作者: 喜欢喝冰茶 时间: 2013-10-11 23:06

chalet 发表于 2013-10-10 22:06
3 ^# ]. z1 S: E' m" Q5 T8 H% U; |欢迎欢迎。, n9 p" ^! I3 z( G5 k

8 F' W, C% @4 O7 M1 Y如果说硬要分类，这个应该还是属于生物信息学领域吧，在科教学圃应该很对口啊。

握握手，看起来也是生物计算的啊，现在在做什么？

还没想好怎么写，涉及的范围得控制一下，要不太大了，而且需要用些篇幅介绍一下疾病得复杂性，像癌症，这个得加好多分子遗传方面的科普，否则的话会很难理解分子诊断方面所面临的挑战。

昨天刚在八卦里贴了一个，http://www.aswetalk.org/bbs/thread-25733-1-1.html，这是一个很好的分子诊断的例子，并且符合现代医学的发展趋势。以后尽可能的在八卦里发一些小东西，最后写的东西应该都能用的上，慢慢来吧。

作者: chalet 时间: 2013-10-12 10:29

喜欢喝冰茶发表于 2013-10-11 23:06
6 N$ M/ c$ W: e$ f) i握握手，看起来也是生物计算的啊，现在在做什么？( S& P' n$ b, f
! q5 E' |( i) U8 G
还没想好怎么写，涉及的范围得控制一下，要不太大了， ...

我可不是作生物计算的，是学临床医学出身的，而数学正是我的致命伤，哭啊~~~
那是上一轮生物技术泡沫的时候，进了国内一家生物技术公司，稍微了解了点BLAST，2003年就离开那个公司，也离开这个行业了。
对于用基因技术研究人体奥秘的价值，可以说我的认识也经历了起起落落的波折。90年代一直到本世纪初，不管是上课听到的还是看到的资料，都非常乐观，好像用测序把基因序列搞清楚了就能解决一切问题，像找到了终极解决方案一样。可是接触到这个行业后，才理解这个编码其实和天书有的一比，它具体在说什么，还需要非常复杂的分析才可能稍有理解。结合到临床，其实大部分常见病都是多基因病，单靠基因序列数据，人们其实所能做的极其有限。
目前基因测序能够帮助到临床的情况，仍然非常局限，还局限在一些基因层面比较简单的情况下。个人之前以为，这是一个系统工程，基因测序技术和数据挖掘方法是其中一块，这块的发展程度可能已经超出其他领域（说实话我不太懂其他领域包括什么，但是起码觉得对序列的临床相关性，目前还所知甚少）。现在看到你说到已经有些实际的临床应用，非常高兴，希望看到这样的进步日积月累，逐渐改变当前有点进退维谷的医学实践。
关于AML分类标准，我先去学习下。期待你的佳作!

作者: 喜欢喝冰茶 时间: 2013-10-12 15:10

chalet 发表于 2013-10-11 20:29 5 s# b% E+ D! n0 J& o8 B
我可不是作生物计算的，是学临床医学出身的，而数学正是我的致命伤，哭啊~~~
/ J+ E: q! X$ }6 n0 E那是上一轮生物技术泡沫的时 ...

兄弟原来是医生，幸会幸会，我的很多合作者都是MD。

呵呵，03年太早了，HGP刚完成，那会儿还没看出个所以然来。到07年，新一代测序技术引入市场，一场“革命”就真得来了。对于癌症，人们了解的越来越多，这方面TCGA功不可没。

事实上，大家谈论的是分子诊断，而非基因诊断。虽然大多数生物学家和医生仍然以基因作为基本单元考虑疾病，但在做生物医学信息的人看来，基因是个太大的概念，也是太不准确的概念，例如，临床常用的mRNA的表达，一般是以基因为基本单位的。但是，基因里面有exon，如果一个exon正向表达，另一个负向表达，从基因层次上可能没区别，但是其实已经涉及到了isoform或者splicing的问题，也就是蛋白的编码有可能被改变了，自然功能就会发生改变，那么这种异常就可以成为该种疾病的一种特征，也就是biomarker。

幸运的是，越来越多的人开始意识到这个问题。我给医学院代的一门课的听众就是MD student，MD fellow和一些即是医生也是faculty的同学们，大家也越来越意识到新的技术正在颠覆我们的概念。

作者: chalet 时间: 2013-10-12 17:12

喜欢喝冰茶发表于 2013-10-12 15:10
q' o- V R/ b+ s& n4 S兄弟原来是医生，幸会幸会，我的很多合作者都是MD。
1 @ J! J" X6 k4 H; ]) s) V7 b- l& U W- T) b4 ]4 y: \
呵呵，03年太早了，HGP刚完成，那会儿还没看出个所 ...

非常赞同你说的。确实当年我去那家公司的时候，他们拿手的是cDNA表达谱芯片，后面的事实证明，这个层面的发现和病人的实际情况还隔着很远的距离，当时并没有合适的解读手段。

2年前，和当时认识的、仍旧战斗在该领域的朋友聊天，他谈了一些表型基因组学的进展，也让我感受到一些新的进步。

不过，对于分子诊断在临床的大规模应用，相对而言我没有那么乐观，觉得起码有2大障碍需要克服：
1. 分子层面的异常和临床异常之间的相关性如何确认。对于部分简单的疾病，可能一对一的关系会比较容易发现，但是大多疾病是属于异质性、存在多个环节异常的。如何识别出一群有效的标志物、如何明确一个个体究竟是哪些标志物的异常是真实发挥作用的，似乎都不是很容易（好像是K-RAS吧，很好的一个标志物，可是却没有治疗靶标的价值）。在这方面需要大量的临床信息和检测结果的综合分析。但是对这个阶段，似乎大部分医生的兴趣度还不够高，而光靠academic institute里面的医生似乎还不够收集足够的数据。

2. 分子诊断和个体化医学时代，必然需要繁复的基因、蛋白层面的检测，和数量巨大的针对性药物，这与现有的药物开发和营销模式完全不合拍。孤儿药模式不可能成为未来药物治疗的支柱。那么医药企业是否会成为个体化医学的发展阻力呢？对此我是有疑问的。

总之，我相信个体化医学将是最终的方向，但是面对现有研究和诊治体系，个体化医学可能需要现有体系改变目前的游戏规则和流程，我对这一个矛盾的解决途径非常好奇。可以说，有生之年可以目睹这场大戏的上演，也是我们的幸事。

作者: 喜欢喝冰茶 时间: 2013-10-13 15:04

chalet 发表于 2013-10-12 03:12 # M; ]$ Q; o+ D; m: p" A% f5 f
非常赞同你说的。确实当年我去那家公司的时候，他们拿手的是cDNA表达谱芯片，后面的事实证明，这个层面的 ...

cDNA算是经典的array了，该不会在程氏公司吧~_~。现在mRNA的expression，特别是经典的几十个癌症基因的表达，仍然是对一些癌症进行相对早期诊断的手段之一，只不过受益者比较小众而已。

分子诊断在临床上的大规模应用现在确实没开始，但是这方面的工作很早就铺开了，而且很多临床机构已经参加进来。这个月cell上刚发了一篇TCGA网络的作者们有关glioblastoma的文章，还没看完，刚看了个开头，不过又看到一个朋友的名字在上面。除了像Washington Univ at St louis(它有和Johnhopkins，harvard齐名的医学院)，broad institute这样的学术机构(这个机构其实是很应用的)，如果对美国的癌症治疗了解的话，会看到很多著名的医疗机构，诸如sloan-kettering, dana-farber,md anderson, mayo clinic, fred hutchinson等等这些名闻遐迩的癌症中心的临床人员也参与进来。大量的临床信息和分子测量信息被综合考虑加以分析，事实上，TCGA的array数据是公开可以下载的。TCGA因为是NCI直接支持的，资源非常充足。无论是这次的GBM还是五月份在New England Journal of Medicine发表的AML，动辄就是几百个病人一下子上五六个平台同时测量分析，使用了当前最先进的设备和分析手段，知道了很多以前不了解的信息，这些东西势必对以后的应用提供很大的帮助。另外一方面，不仅是对第一个问题的补充，同时也算是回答了第二个问题。那就是现在数得着的药厂，都已经或者正在建立分子诊断部门，而他们的实力绝对不可小觑，只不过人家闷声发财罢了。就我所了解的情况，很多医生还是很感兴趣的，不仅是美国的，还有中国的，因为已经有越来越多的病例是依赖新技术而得到治疗的。

然而，诚如你所说，癌症的heterogeneous特性，使得这一领域所面临的挑战远远超过了我们的想象。在AML的研究中，recurrent 的定义是5%，可是看看有多少variants是可以被5%的病人所共享的？这东西不像别的学科，了解的越多，会越来越明朗，而是知道的越多，会越来越困惑。没办法，人自己设计的东西和自然选择出来的东西，论精巧和控制真的不能比。但是，现在的努力仍然对以后是有很大帮助的。例如现在被部分人批评的GWAS研究，不可否认那东西烧了不少钱，而结果相对有限。但是23&me能卖100块钱的疾病风险评估的基础，不就是GWAS鉴定出来的一两千个和疾病关联的SNP吗？

坦白的说，不要说personalized medicine了，就是diagnosis在我们这代人的有生之年都没戏，因为疾病太复杂。不要试图解决所有的问题，但是现在的工作仍然有很大的意义。例如，根据NCI和ACA的数据，美国刚刚过去的财年，确诊了大约一万五千个AML病人，但是也死掉了一万多点儿的病人，当然不都是这一万五里的。你也许知道这种癌症是现在常规手段根本无法诊断和发现的，因为癌细胞在骨髓里。所以不要指望能一下子解决它，但是如果现在的工作能够使一百个病人受益，虽然统计上没有什么意义，毕竟不到1%，但是对这一百个家庭，那又意味着什么？

作者: chalet 时间: 2013-10-14 11:20

喜欢喝冰茶发表于 2013-10-13 15:04
6 P2 J1 m& }7 M( f* _# A: q# N* IcDNA算是经典的array了，该不会在程氏公司吧~_~。现在mRNA的expression，特别是经典的几十个癌症基因的 ...

我对当前这个领域的研究有2个观点：
1. 当前这种研究思路，有点花大本钱做剥丝抽茧的小事的味道。一方面进步是实际存在的，另一方面又是相对片面和局限的，效率不高甚至低下。当然，这也是没有其他选择的，只能从每一个细节处着手，用蚂蚁啃骨头的办法一点点来。之前一个肺癌医生这么看待这个问题：靶向治疗药物每个针对的都是小众，虽然小，但是他们一个接一个在肺癌这个大盘子里切出小片来，积少成多，总有一天，靶向治疗会成为覆盖大多数人的有效方法。

2. 个体化医学是方向，但是我们也不能奢望会有一整套的新理论新方法完全取代现在的治疗手段，那肯定是遥遥无期的事情。将现有治疗手段和个体化前沿研究的成果相结合，这个应该是更实际的路径。比如我感觉最近对靶向药物的期待已经不像几年前那么乐观，应该说是更加认识到它们的局限性了。那么现在这个情况下，有必要加强对传统手段的优化研究，比如通过对患者个体化特质的分析对传统化疗进行优化。最近听说有些单位已经在做患者化疗药物的AUC监测，这就是用现成手段进行个体化医学实践的例子，期待他们能脚踏实地，有所收获。

作者: 喜欢喝冰茶 时间: 2013-10-15 14:25

chalet 发表于 2013-10-13 21:20
# ~; U! X0 ^" l: ?; \我对当前这个领域的研究有2个观点：2 E% y' T( V0 }1 S X. e* p% V
1. 当前这种研究思路，有点花大本钱做剥丝抽茧的小事的味道。一方面 ...

呵呵，那你觉得什么样的思路才是花小钱办大事的呢？HGP刚开始的时候，也有人觉得是浪费钱。没有大量的片面，何来所谓的全面。这样做的动机，其实很简单，就是大量的证据表明，很多疾病，特别是癌症，大部分获得性癌症病人的DNA，RNA序列上有非常明显的异常，有些时候，连形态学上都能看出来。那么大家自然就想既然生出来是“正常的”，发病了就不正常了，所以DNA／RNA序列上的变化一定是时间的“函数”。既然现在没什么别的技术系统地可以用于癌症的早期诊断，那分析DNA/RNA异常大概是最可能也是最现实的方法。

从来没有人，再没有确认更好的方法前，去准备取代现在的手段。而且一定要明确得是，基本上，现在得研究给出的是风险，而非确认。毕竟DNA/RNA上观测到的异常只是癌症一个因素，癌症的发展还和“环境”有很大关联的。对现在这种diagnosis方面的工作，相当一部分人存在一种误区。有点像一些实验生物的人看计算生物学一样，开始以为这玩意儿什么都能干，结果发现蛮不是那回事，然后就弃之不用。都不想想，真要是啥都能做，做实验的不早失业了？要真是没用，这门学科也早死了。整天吵吵garbage in garbage out的同学们，你们怎么知道人家input的就是garbage呢？远在这帮做实验的同学们去质疑计算是否正确之前，做biocomputing的早想到了这个问题，并且已经从实验中去寻找间接证据去确认了。把新生的东西当成一种手段就是了，不要排斥，和已有的成熟手段一起使用就行，只要能提高癌症病人的生存率，那每一种方法都有意义。事实上新技术在临床上的成功应用都是和其他手段一起使用的，毕竟这些技术不能治疗，像著名的Nic案例，真正的治疗手段仍然是骨髓移植，但是新技术对最后确定手术起了很大的作用。

作者: 一叶飞刀 时间: 2014-11-15 21:01
关于字符串匹配，应当已经解决完毕了，大概不会有更高级的算法了。

从S中找ss简单匹配算法为用ss的第一个字母对齐S，逐一比对，直到不匹配或者完全匹配，然后ss的第一个字母对齐S的第二个字母，如此反复，算法复杂度为S和ss长度的乘积，即无论哪个字符串长度增加一倍，执行时间大体增加一倍。

高级算法是，既然以前已经比较过了，那么后面的比较就可以利用前面失败的匹配所收集的信息，从而下次匹配时直接往前跳，比如一开始从S的第一个字符跟ss的第一个字符比对，比对到第十个字符，失配，那么由于已经进行了九个字符的匹配且能对的上，那么以前已经匹配过的九个字符就不要重复匹配了，第十个字符根据某种规则直接跟ss中的某一个字符匹配。这种算法的复杂度为S的长度。由于要匹配，至少要遍历S一次，所以这个最多在细节上改进，不会有本质的改进。

以上，任何一本数据结构教材，比如清华版的数据结构与算法，均有提及

作者: 喜欢喝冰茶 时间: 2015-1-5 21:18

一叶飞刀发表于 2014-11-15 07:01( R' x3 U- f/ S3 u
关于字符串匹配，应当已经解决完毕了，大概不会有更高级的算法了。/ A X) |+ Z+ S. J8 v; a

7 q ^% X: h9 @: V0 C5 U" D从S中找ss简单匹配算法为用ss的第一个 ...

嗯，perfect match不是大问题，问题在于容错匹配，甚至有时候只有头上或者尾巴上的部分匹配。这部分在RNA seq或者DNA seq中的translocation中应用很广。

欢迎光临爱吱声 (http://www.aswetalk.net/bbs/)