字符串匹配

喜欢喝冰茶

字符串匹配，string match，这个是计算机里面常见的问题，例如：
/ M" q2 X5 P( s" s
: t7 w. j; c* `7 C7 ~2 vstring1: TACGGCATGGCTATCGTAGCTAG
: N$ N1 n$ K6 E0 Q- Q- \
string2: GCTAT
  C" g6 a0 p" X/ g$ C/ t; a! o& g
2 p% b" }) l" z( {/ Y/ E9 E# V要求在string1里找到string2的位置，如果存在多个的话，都要找出来。
1 n2 n" m$ L/ M$ i7 `) m
可以自己估计一下时间复杂度，真实的例子是，String1长达3billion，或者6个billion。string2长约一、二百，但是数目可以是以billion计的。

先扛着。

晨枫

怎么感觉这个和基因研究有关？识别基因里的某种特征？

MacArthur

晨枫 发表于 2013-10-6 16:16
怎么感觉这个和基因研究有关？识别基因里的某种特征？

( B) \: D) @; k0 y这就是基因BLAST算法的标准定义嘛。。。
! g  X& d4 x! [! Q9 n  E
Google ＂Blast算法＂，一堆开源程序。

晨枫

MacArthur 发表于 2013-10-6 16:17
+ m, G; g- Q. G这就是基因BLAST算法的标准定义嘛。。。
1 K6 g) Q) O0 l, O& \
7 r/ p9 X$ g4 @1 zGoogle ＂Blast算法＂，一堆开源程序。

# j( n) }9 L9 j莫非麦帅也是干这一行的？不然怎么会这么熟悉？

假如十八

晨枫 发表于 2013-10-7 07:21
4 ?' [+ Z5 Z# {, c; f莫非麦帅也是干这一行的？不然怎么会这么熟悉？

8 s2 F8 z! M# e  X这都不用动手写吧？正则表达式很多语言都支持啊

晨枫

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

) }) L, h- N% X4 {: k5 s有可能是普通的bubble sort和quick sort之间的差别？也就是说，普通算法的效率不适合特别大的海量比较计算？

冰蚁

老兵有个群组，软件人家。

巴巴爸爸

MacArthur 发表于 2013-10-7 06:17
( h8 Y4 t: _; Y2 z; Q4 p7 x. K这就是基因BLAST算法的标准定义嘛。。。

) f4 @! w, ^: H0 }1 ~" lGoogle ＂Blast算法＂，一堆开源程序。

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

喜欢喝冰茶

最野蛮也是最简单的办法：一个一个比。

* T* `' W0 ^9 ]2 T  I8 h

string1: TACGGCATGGCTATCGTAGCTAG

2 i: M4 G5 M) h4 P  {string2: GCTAT
5 @( t: Q: E& n3 k4 v- E* p, Y/ Y
要求在string1里找到string2的位置，如果存在多个的话，都要找出来。

9 M& V) I  z7 L' F  f- s- ?0 z
; C: }  p: m2 O6 P! r' \9 q拿string2和string1比，至少需要比string1的长度减去string2的长度再加1次。在实际应用中，如果string1的长度是10^9，而string2只有一二百，那么做一次基本上就是比10^9次。当然如果很幸运，string2在string1开始的地方，那一次就够了。所以平均来说，要比10^9／2次，也就是O(10^9)。

9 I! i! n* r  h* ^. y" K7 E! }但是如果实际情况中，有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年！！！人都死几次还没比完，太郁闷了，所以不可接受。

3 U2 p3 p' `% s( T# a那如果是这个样子
0 S7 |/ r2 D% v0 R3 t
9 V6 X. B8 n  nstring1: AAAAAATTTTCCCCCGGGTTTTAAAACCCCCCGG
. n4 [1 i: \5 {: wstring2: TTAAA

0 y5 u8 q% s7 s: o# Y5 u, @) ?' z是不是会快很多？

! S! M+ D4 d2 d. Y继续扛。

qiuwen777

喜欢喝冰茶 发表于 2013-10-7 09:01
0 P% K9 Q8 g0 W! D  }最野蛮也是最简单的办法：一个一个比。

( s) x" C& b2 v帮你顶一下。很多问题，看起来很简单，但是在数据量大的情况下，根本不是那么回事。
+ y6 V- m' F* h/ i0 ?9 p& w这可以产生很多计算机专家。
' b2 p7 g& }" u对于算法的问题，一般我都躲着。

喜欢喝冰茶

1 u9 i7 ?5 p6 J% D- D8 A2 n

如果两个字符串是这个样子
! F& T: Q1 P& U' }6 O: B
4 B& v, ?/ d7 f; _" J* u2 Mstring1: AAAAAATTTTCCCCCGGGTTTTAAAACCCCCCGG
. l: Q4 [$ \/ Dstring2: TTAAA

& {+ R  k1 }- {
4 L- U+ G1 b. ?当然要省很多时间，因为不需要对string1一个一个比了！！！
& V9 k3 ^& ]' t0 p: c$ f4 B
string1可以写成：
长度 字符 起始位置
" b* z6 r& ?& U4 C8 q  i6      A     1
4      T     7
5      C     11
4 `3 K0 w! w( j3      G     16
4      T     19
3 C, F) [& H* \1 S+ L% `5 z& d* B......
. A9 S+ Q6 |8 q; \- M5 @
所以当用string2去比的时候，一开始根本就不用考虑字符为A，G，C的行，因为string2开始是T。因此在这个例子中，不需要去检查string1的每个位置，而是非常有限的几个位置，所以可以省很多时间。
& f  w0 _3 ]( z9 I' H+ f( G
% U! I( M8 U! N  h- a1 n7 l. {' U那么如果存在一种这样的转换方法能够将主贴里的字符串转化成这种，势必会省很多时间。有这样一种方法吗？哪里去找？

0 H* u  l) u; ?5 Q+ x$ d( f; V如果你是有心人，你觉得这个东西最常用在哪里？

对了，文件压缩。

' E2 K3 E4 O$ K7 {9 T事实上，真正的解决方法就是借鉴了最早用于文件压缩的一种算法，称为Burrows－Wheeler Transform，又称block-sorting compression。这是当年在DEC工作的Michael Burrows和David Wheeler发明的，所以以他们的名字命名，bzip2的压缩文件就是基于该算法的。它的转换其实很简单，如果感兴趣大家可以google／wiki（wikipedia上很详细的操作细节）上去看细节，但简单的来说，就是把一个字符串头围相接，不停的移动一位，然后排序，最后取出最后一列就行了。Burrows－Wheeler Transform的特性就是转换后的字符串相对于原始字符串含有大量的重复字符片段，所以就可以使得我们的问题变的相对快捷。
2 H* y  j8 c- }% z) c
那么是否就十全十美，万事大吉了呢？这个需要从实际的具体需求来看。
( T0 V! v# K1 [4 y& A* _& L
9 P5 A$ [  c  S扛吧，没什么好说的。

5 H8 m) R2 I6 ?, |4 z# a7 J

喜欢喝冰茶

MacArthur 发表于 2013-10-6 16:17
* E' C  m9 J. _/ |& ~这就是基因BLAST算法的标准定义嘛。。。
5 R+ G$ m6 j; h+ o% s5 R
Google ＂Blast算法＂，一堆开源程序。

$ x1 [" u; J7 }4 K+ gblast并非只是解决基因的问题，蛋白同样适用，只不过相对于DNA／RNA而言，蛋白质要复杂得多。

MacArthur

喜欢喝冰茶 发表于 2013-10-6 21:38
8 \& _+ H5 m2 t- \! Yblast并非只是解决基因的问题，蛋白同样适用，只不过相对于DNA／RNA而言，蛋白质要复杂得多。 ...

不明觉厉。。。 上Billion字节的操作，想想就头大。。。 这个规模是不是得上并行计算了？
: C2 n. _. o: S$ z. _7 B

喜欢喝冰茶

MacArthur 发表于 2013-10-6 21:35
: ^/ ^3 {( ?" Q1 S& t4 E) t不明觉厉。。。 上Billion字节的操作，想想就头大。。。 这个规模是不是得上并行计算了？
/ S  B5 [; n$ o4 |  k6 @  } ...

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

老芒

5 ^, |3 _8 G0 h4 j- D7 A
这样的短贴适合聊天版。

martian

喜欢喝冰茶 发表于 2013-10-7 10:35
* l1 Q! x' Y) [& t6 H% E; Q% a当然要省很多时间，因为不需要对string1一个一个比了！！！

string1可以写成：

, t/ O4 c, O/ g" K; P是要找pattern

Ensembl就用了这种数据压缩方法，
, C. ?! _; J( _4 v; ~AAATTCCGG
5 x2 E& ]- O: K3 ?" QA3T2C2G2

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

喜欢喝冰茶

已经有同校指出了blast，一个用于对生物大分子的测序程序。这东西正式诞生于1990年，同年人类基因组计划启动。它不仅可以用于DNA/RNA的测序，还可以对蛋白测序。六年前在河里曾经写过一个搭积木的小玩意儿，其中涉及到利用计算方法来预测实验中很难测量的蛋白质空间结构，最有效的计算方法就是同源模型。在这个模型里面，我们允许寻找的字符串,string2可以不用严格的和string1，也就是模板序列，匹配的。换句话说，就是字符串匹配是容错的。具体到主贴里提到的真实问题的挑战，就是模板字符串是人类的基因组（genome），单链长达3billion结构单位，也就是3billion的字符长度，而DNA是双链的，也就是6B的长度。想一想，每个人都是unique的，所以即使都是“健康人”，每个人的基因组都不会完全一样，因此，这种字符串的匹配一定是允许错误的，否则的话，如果大家都一样，即使算法速度再慢都不是问题，因为只做一次，从时间复杂度上，就是0。
  F9 Q0 A; q" H
那么如果考虑容错的匹配，基于bwt方法的算法将面临一个巨大的挑战，因为BWT是严格转换的，可是容错的实际需要，就要考虑转换前和转换后的字符串的错误问题，这会使的问题非常复杂。因此，现在的解决方案就是，当我们需要更多的关注容错的问题时，我们仍然使用传统的，也就是blast所使用的Smith－Waterman算法。具体的细节，感兴趣的可以google／wiki，基本来讲，这是一种被称之为动态编程的计算机算法，可以很好的考虑容错问题，诸如substitution、insertion、deletion或者indel（也就是insertion和deletion的混合体），而这些“错误”，则广泛的存在于病人的基因组中，特别是癌症基因组。当然，现在所使用的smith－waterman基于的方法都是修改了的，主要是计算机算法上的加速，诸如hash的SW算法。

+ `) k( r, d) x! W* e* ~) u但是，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序列的检测成为新生儿的常规检查。

喜欢喝冰茶

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

chalet

喜欢喝冰茶 发表于 2013-10-9 10:43
这个帖子里的东西，看起来似乎是一个简单的计算问题，但是却很可能是一场改变人类健康革命的基础。正是由于 ...

- T2 m8 x* L4 H6 `) l. @欢迎欢迎。
2 t. D( v& c1 I
0 k" J$ }7 G0 Z+ P$ W: _! y$ I如果说硬要分类，这个应该还是属于生物信息学领域吧，在科教学圃应该很对口啊。
, S& S) \8 B! \2 s
1 y2 C$ F/ F/ x8 d% X+ T使用NCBI网站上的BLAST都是10多年前的事情了，一眨眼人都老了。。。

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

喜欢喝冰茶

chalet 发表于 2013-10-10 22:06
欢迎欢迎。
- T' w/ x3 q! V8 J9 F- o- W
, O8 ?- Y5 |/ _/ X" d如果说硬要分类，这个应该还是属于生物信息学领域吧，在科教学圃应该很对口啊。

' V- q( c* T6 s+ F+ D$ P握握手，看起来也是生物计算的啊，现在在做什么？
! I6 Z1 ?' W3 E
还没想好怎么写，涉及的范围得控制一下，要不太大了，而且需要用些篇幅介绍一下疾病得复杂性，像癌症，这个得加好多分子遗传方面的科普，否则的话会很难理解分子诊断方面所面临的挑战。

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