字符串匹配

chalet

喜欢喝冰茶 发表于 2013-10-11 23:06
. M9 k# V. ~% g握握手，看起来也是生物计算的啊，现在在做什么？
9 A, S, ~9 Z0 ~& b' a: p
9 C$ J1 H3 A- d/ \+ I' w5 j3 Q还没想好怎么写，涉及的范围得控制一下，要不太大了， ...

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

喜欢喝冰茶

chalet 发表于 2013-10-11 20:29
我可不是作生物计算的，是学临床医学出身的，而数学正是我的致命伤，哭啊~~~
那是上一轮生物技术泡沫的时 ...

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

呵呵，03年太早了，HGP刚完成，那会儿还没看出个所以然来。到07年，新一代测序技术引入市场，一场“革命”就真得来了。对于癌症，人们了解的越来越多，这方面TCGA功不可没。
# Y" l$ V# X8 P8 f9 V; c
) K  k$ b2 p( p$ D' Y" x事实上，大家谈论的是分子诊断，而非基因诊断。虽然大多数生物学家和医生仍然以基因作为基本单元考虑疾病，但在做生物医学信息的人看来，基因是个太大的概念，也是太不准确的概念，例如，临床常用的mRNA的表达，一般是以基因为基本单位的。但是，基因里面有exon，如果一个exon正向表达，另一个负向表达，从基因层次上可能没区别，但是其实已经涉及到了isoform或者splicing的问题，也就是蛋白的编码有可能被改变了，自然功能就会发生改变，那么这种异常就可以成为该种疾病的一种特征，也就是biomarker。
: N" q* G' E9 ?& g# b2 {0 x
幸运的是，越来越多的人开始意识到这个问题。我给医学院代的一门课的听众就是MD student，MD fellow和一些即是医生也是faculty的同学们，大家也越来越意识到新的技术正在颠覆我们的概念。

chalet

喜欢喝冰茶 发表于 2013-10-12 15:10
- Z7 a, A! m5 E' |; _. J$ j# f兄弟原来是医生，幸会幸会，我的很多合作者都是MD。

4 C$ N& Z( o* L2 S+ p呵呵，03年太早了，HGP刚完成，那会儿还没看出个所 ...

* f6 W3 e  ~& W, s/ K0 i" R% K非常赞同你说的。确实当年我去那家公司的时候，他们拿手的是cDNA表达谱芯片，后面的事实证明，这个层面的发现和病人的实际情况还隔着很远的距离，当时并没有合适的解读手段。
* z" ^& t- M0 b9 B! g! @
2年前，和当时认识的、仍旧战斗在该领域的朋友聊天，他谈了一些表型基因组学的进展，也让我感受到一些新的进步。
: a9 K' R+ b8 L( _: P
不过，对于分子诊断在临床的大规模应用，相对而言我没有那么乐观，觉得起码有2大障碍需要克服：
1. 分子层面的异常和临床异常之间的相关性如何确认。对于部分简单的疾病，可能一对一的关系会比较容易发现，但是大多疾病是属于异质性、存在多个环节异常的。如何识别出一群有效的标志物、如何明确一个个体究竟是哪些标志物的异常是真实发挥作用的，似乎都不是很容易（好像是K-RAS吧，很好的一个标志物，可是却没有治疗靶标的价值）。在这方面需要大量的临床信息和检测结果的综合分析。但是对这个阶段，似乎大部分医生的兴趣度还不够高，而光靠academic institute里面的医生似乎还不够收集足够的数据。
% h# a& I8 @7 W- a( `0 j8 R6 l0 }
; o7 t: m% n1 i: F- T1 W2. 分子诊断和个体化医学时代，必然需要繁复的基因、蛋白层面的检测，和数量巨大的针对性药物，这与现有的药物开发和营销模式完全不合拍。孤儿药模式不可能成为未来药物治疗的支柱。那么医药企业是否会成为个体化医学的发展阻力呢？对此我是有疑问的。
+ n9 f+ C" }+ p% V9 G+ e
总之，我相信个体化医学将是最终的方向，但是面对现有研究和诊治体系，个体化医学可能需要现有体系改变目前的游戏规则和流程，我对这一个矛盾的解决途径非常好奇。可以说，有生之年可以目睹这场大戏的上演，也是我们的幸事。

喜欢喝冰茶

chalet 发表于 2013-10-12 03:12
非常赞同你说的。确实当年我去那家公司的时候，他们拿手的是cDNA表达谱芯片，后面的事实证明，这个层面的 ...

7 ^8 o6 z) l) X' F
9 h; B, b  e1 \% ]
cDNA算是经典的array了，该不会在程氏公司吧~_~。现在mRNA的expression，特别是经典的几十个癌症基因的表达，仍然是对一些癌症进行相对早期诊断的手段之一，只不过受益者比较小众而已。
* ~' i+ V, k& r3 ]3 i& y
分子诊断在临床上的大规模应用现在确实没开始，但是这方面的工作很早就铺开了，而且很多临床机构已经参加进来。这个月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吗？
. z  ^8 v" n: D: Y. S
& x) a5 N% I; z3 q坦白的说，不要说personalized medicine了，就是diagnosis在我们这代人的有生之年都没戏，因为疾病太复杂。不要试图解决所有的问题，但是现在的工作仍然有很大的意义。例如，根据NCI和ACA的数据，美国刚刚过去的财年，确诊了大约一万五千个AML病人，但是也死掉了一万多点儿的病人，当然不都是这一万五里的。你也许知道这种癌症是现在常规手段根本无法诊断和发现的，因为癌细胞在骨髓里。所以不要指望能一下子解决它，但是如果现在的工作能够使一百个病人受益，虽然统计上没有什么意义，毕竟不到1%，但是对这一百个家庭，那又意味着什么？

' b% i. P& L& `2 `+ O
6 S2 l& Z4 t! p# F8 w

$ }9 d7 H5 b1 x( p
0 Y5 y* |0 G  {* _, n: o

chalet

喜欢喝冰茶 发表于 2013-10-13 15:04
cDNA算是经典的array了，该不会在程氏公司吧~_~。现在mRNA的expression，特别是经典的几十个癌症基因的 ...

我对当前这个领域的研究有2个观点：
0 |, L2 Q) K: \* [8 V8 i1. 当前这种研究思路，有点花大本钱做剥丝抽茧的小事的味道。一方面进步是实际存在的，另一方面又是相对片面和局限的，效率不高甚至低下。当然，这也是没有其他选择的，只能从每一个细节处着手，用蚂蚁啃骨头的办法一点点来。之前一个肺癌医生这么看待这个问题：靶向治疗药物每个针对的都是小众，虽然小，但是他们一个接一个在肺癌这个大盘子里切出小片来，积少成多，总有一天，靶向治疗会成为覆盖大多数人的有效方法。
6 \% l6 K; s/ Z5 N
) R( u" S2 ?& A2. 个体化医学是方向，但是我们也不能奢望会有一整套的新理论新方法完全取代现在的治疗手段，那肯定是遥遥无期的事情。将现有治疗手段和个体化前沿研究的成果相结合，这个应该是更实际的路径。比如我感觉最近对靶向药物的期待已经不像几年前那么乐观，应该说是更加认识到它们的局限性了。那么现在这个情况下，有必要加强对传统手段的优化研究，比如通过对患者个体化特质的分析对传统化疗进行优化。最近听说有些单位已经在做患者化疗药物的AUC监测，这就是用现成手段进行个体化医学实践的例子，期待他们能脚踏实地，有所收获。

喜欢喝冰茶

chalet 发表于 2013-10-13 21:20
* A  L: _8 o/ K! ], r" C+ p我对当前这个领域的研究有2个观点：
1. 当前这种研究思路，有点花大本钱做剥丝抽茧的小事的味道。一方面 ...

1 M( i( D' |3 f9 ]呵呵，那你觉得什么样的思路才是花小钱办大事的呢？HGP刚开始的时候，也有人觉得是浪费钱。没有大量的片面，何来所谓的全面。这样做的动机，其实很简单，就是大量的证据表明，很多疾病，特别是癌症，大部分获得性癌症病人的DNA，RNA序列上有非常明显的异常，有些时候，连形态学上都能看出来。那么大家自然就想既然生出来是“正常的”，发病了就不正常了，所以DNA／RNA序列上的变化一定是时间的“函数”。既然现在没什么别的技术系统地可以用于癌症的早期诊断，那分析DNA/RNA异常大概是最可能也是最现实的方法。
6 d" R$ n5 j5 _- g+ J1 m# `
从来没有人，再没有确认更好的方法前，去准备取代现在的手段。而且一定要明确得是，基本上，现在得研究给出的是风险，而非确认。毕竟DNA/RNA上观测到的异常只是癌症一个因素，癌症的发展还和“环境”有很大关联的。对现在这种diagnosis方面的工作，相当一部分人存在一种误区。有点像一些实验生物的人看计算生物学一样，开始以为这玩意儿什么都能干，结果发现蛮不是那回事，然后就弃之不用。都不想想，真要是啥都能做，做实验的不早失业了？要真是没用，这门学科也早死了。整天吵吵garbage in garbage out的同学们，你们怎么知道人家input的就是garbage呢？远在这帮做实验的同学们去质疑计算是否正确之前，做biocomputing的早想到了这个问题，并且已经从实验中去寻找间接证据去确认了。把新生的东西当成一种手段就是了，不要排斥，和已有的成熟手段一起使用就行，只要能提高癌症病人的生存率，那每一种方法都有意义。事实上新技术在临床上的成功应用都是和其他手段一起使用的，毕竟这些技术不能治疗，像著名的Nic案例，真正的治疗手段仍然是骨髓移植，但是新技术对最后确定手术起了很大的作用。

' O4 m9 r  r8 g
0 S# p/ N  ]8 G& H8 Y) k7 L

一叶飞刀

关于字符串匹配，应当已经解决完毕了，大概不会有更高级的算法了。
; y5 {. j& U: t5 a) V
1 x" i6 I6 O) n' q从S中找ss简单匹配算法为用ss的第一个字母对齐S，逐一比对，直到不匹配或者完全匹配，然后ss的第一个字母对齐S的第二个字母，如此反复，算法复杂度为S和ss长度的乘积，即无论哪个字符串长度增加一倍，执行时间大体增加一倍。
! G6 ?1 p2 p. E
4 k/ C3 i/ w( `" u0 p  ~( K高级算法是，既然以前已经比较过了，那么后面的比较就可以利用前面失败的匹配所收集的信息，从而下次匹配时直接往前跳，比如一开始从S的第一个字符跟ss的第一个字符比对，比对到第十个字符，失配，那么由于已经进行了九个字符的匹配且能对的上，那么以前已经匹配过的九个字符就不要重复匹配了，第十个字符根据某种规则直接跟ss中的某一个字符匹配。这种算法的复杂度为S的长度。由于要匹配，至少要遍历S一次，所以这个最多在细节上改进，不会有本质的改进。
9 g  v5 D/ o& b3 H
4 i) X3 p# K$ D# o以上，任何一本数据结构教材，比如清华版的数据结构与算法，均有提及

喜欢喝冰茶

一叶飞刀 发表于 2014-11-15 07:01
5 L3 t6 q+ I6 r: [  W7 p关于字符串匹配，应当已经解决完毕了，大概不会有更高级的算法了。
( p; ~7 }# F4 b# f
4 Z' g" q% }% n5 w( G$ b2 O从S中找ss简单匹配算法为用ss的第一个 ...

6 `! M1 P. K+ B% N% m: V3 W) ]嗯，perfect match不是大问题，问题在于容错匹配，甚至有时候只有头上或者尾巴上的部分匹配。这部分在RNA seq或者DNA seq中的translocation中应用很广。