设为首页收藏本站
开启辅助访问 切换到宽版

爱吱声

 找回密码
 注册
搜索
爱吱声»广场 › 研究生院 › 科教学圃 › 字符串匹配
12下一页
返回列表 发新帖
查看: 8426|回复: 27
打印 上一主题 下一主题

[科技前沿] 字符串匹配

[复制链接]
喜欢喝冰茶

该用户从未签到
跳转到指定楼层
楼主
发表于 2013-10-7 04:13:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
本帖最后由 橡树村 于 2013-10-15 15:48 编辑
; H  Q  g5 K" o- L  o
4 }; E* q, k( m7 N. c字符串匹配，string match，这个是计算机里面常见的问题，例如：& X# R2 |7 G4 @: o' y$ ?4 ]

2 N, I2 D5 n. b4 B9 K+ c; Sstring1: TACGGCATGGCTATCGTAGCTAG, @& G/ P  A3 U8 _7 y* {

, V& w0 Q4 s0 c8 Zstring2: GCTAT
- ?7 R( T( R2 d, Q. h' L  A  D9 d, F/ G% A, j- s9 k. z
要求在string1里找到string2的位置，如果存在多个的话，都要找出来。: A( I* [: ?% V2 s
( G% |* g  u# V; ~, q  }+ l
可以自己估计一下时间复杂度，真实的例子是，String1长达3billion，或者6个billion。string2长约一、二百，但是数目可以是以billion计的。
" X% C, Z, T" Y7 e( |, G
7 k1 }8 i0 G& c: w2 O. R9 i先扛着。
回复

使用道具 举报

晨枫

该用户从未签到
沙发
发表于 2013-10-7 05:16:35 | 只看该作者
怎么感觉这个和基因研究有关？识别基因里的某种特征？

点评

喜欢喝冰茶
这个不只是和基因有关。  发表于 2013-10-7 10:39
回复 支持 反对

使用道具 举报

MacArthur
  • TA的每日心情
    开心
    2023-3-1 00:08

    • 签到天数: 2397 天

    [LV.Master]无

    板凳
    发表于 2013-10-7 06:17:53 | 只看该作者
    晨枫 发表于 2013-10-6 16:16
    " \) b+ I! |) L怎么感觉这个和基因研究有关？识别基因里的某种特征？

      W4 `" i4 o& t0 C: I( Q( P  C- L这就是基因BLAST算法的标准定义嘛。。。; `4 w4 r1 x* G3 R- Q( X# p2 u7 |$ o7 C

    " P* M" j: G2 H& M- z5 hGoogle ＂Blast算法＂，一堆开源程序。
    3 x' }6 s) |3 T4 G

    点评

    喜欢喝冰茶
    呵呵，这只是blast要解决的问题，而非定义。事实上，blast很少使用，因为首贴里的实际问题，用blast在可以容忍的时间里是完不成的，你可以估算一...  发表于 2013-10-7 08:55
    回复 支持 反对

    使用道具 举报

    晨枫

    该用户从未签到
    地板
    发表于 2013-10-7 07:21:39 | 只看该作者
    MacArthur 发表于 2013-10-6 16:17
    $ y$ p( P2 w  x2 d3 Y& y" f( A6 r这就是基因BLAST算法的标准定义嘛。。。1 }+ q3 h- A* r& R) t. {( }* c+ g
    ; y6 X/ f% B" ?4 t
    Google ＂Blast算法＂，一堆开源程序。

    - A' h. G( @2 a/ u) K( I莫非麦帅也是干这一行的？不然怎么会这么熟悉？

    点评

    喜欢喝冰茶
    麦帅好职业  发表于 2013-10-7 20:51
    MacArthur
    Work with bioinformatician  发表于 2013-10-7 11:31
    回复 支持 反对

    使用道具 举报

    假如十八

    该用户从未签到
    5#
    发表于 2013-10-7 07:28:07 | 只看该作者
    晨枫 发表于 2013-10-7 07:21 ; c/ m# }+ u& d/ [1 k
    莫非麦帅也是干这一行的？不然怎么会这么熟悉？
    : G9 T; ]8 D" {4 h, {
    这都不用动手写吧？正则表达式很多语言都支持啊

    点评

    喜欢喝冰茶
    这世界上很多东西，用就好了。  发表于 2013-10-7 10:37
    回复 支持 反对

    使用道具 举报

    晨枫

    该用户从未签到
    6#
    发表于 2013-10-7 07:29:33 | 只看该作者
    假如十八 发表于 2013-10-6 17:28
    ) N. x5 u. n$ s5 {, b" z这都不用动手写吧？正则表达式很多语言都支持啊
    1 C- x- D' b& L  z
    有可能是普通的bubble sort和quick sort之间的差别？也就是说，普通算法的效率不适合特别大的海量比较计算？

    点评

    喜欢喝冰茶
    往下看，有点儿意思。  发表于 2013-10-7 10:37
    回复 支持 反对

    使用道具 举报

    冰蚁
  • TA的每日心情
    擦汗
    2019-6-16 23:34

    • 签到天数: 1277 天

    [LV.10]大乘
    7#
    发表于 2013-10-7 07:33:11 | 只看该作者
    老兵有个群组，软件人家。

    点评

    喜欢喝冰茶
    谢谢提醒，有机会看看。  发表于 2013-10-7 08:57
    回复 支持 反对

    使用道具 举报

    巴巴爸爸
  • TA的每日心情
    开心
    2016-4-24 12:49

    • 签到天数: 7 天

    [LV.3]辟谷
    8#
    发表于 2013-10-7 08:38:30 | 只看该作者
    MacArthur 发表于 2013-10-7 06:17
    " |$ t" C7 R) f* ^5 G9 |这就是基因BLAST算法的标准定义嘛。。。7 F9 R$ O  z# m1 L! E
    * K" I" C0 i' s7 H
    Google ＂Blast算法＂，一堆开源程序。
    9 ~. l# x; [: n
    blast......恍若隔世，你不说我都忘了曾经有那么一段时间天天跟这个较劲。。。。

    点评

    MacArthur
    对葵花开始滔滔江水。。。  发表于 2013-10-7 11:36
    喜欢喝冰茶
    是吗？做什么呢？  发表于 2013-10-7 10:36
    回复 支持 反对

    使用道具 举报

    喜欢喝冰茶

    该用户从未签到
    9#
     楼主| 发表于 2013-10-7 09:01:33 | 只看该作者
    最野蛮也是最简单的办法：一个一个比。
    7 |& |3 ?( S( }% s  U% e! x( F$ {0 e. V0 o
    string1: TACGGCATGGCTATCGTAGCTAG' I8 d/ l1 ~% D4 Y5 A
    " ]2 i3 p( a9 @
    string2: GCTAT
      t7 t; r: M4 \( a# L. H
    6 T0 `& ?' @& t: J& Q( u: v( e& a要求在string1里找到string2的位置，如果存在多个的话，都要找出来。
    1 n1 |( g: l! `. s0 D1 \8 I$ y; M! i

    . M0 D3 z6 h: z拿string2和string1比，至少需要比string1的长度减去string2的长度再加1次。在实际应用中，如果string1的长度是10^9，而string2只有一二百，那么做一次基本上就是比10^9次。当然如果很幸运，string2在string1开始的地方，那一次就够了。所以平均来说，要比10^9／2次，也就是O(10^9)。
    8 G! }* r! |* F6 a
    8 w/ z+ T4 l! d/ j! g: g- @但是如果实际情况中，有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年！！！人都死几次还没比完，太郁闷了，所以不可接受。
    6 R: @% M) }4 R& r3 ?# w1 o- k  G0 N0 b4 \! \& E* Q: }3 D
    那如果是这个样子7 W4 D/ ?2 m, Y( Y) S) r
    - s% W( R8 K7 @5 r0 p, C# e) M
    string1: AAAAAATTTTCCCCCGGGTTTTAAAACCCCCCGG/ b0 _6 E7 T) @; \$ P
    string2: TTAAA, g5 S7 v0 w, W* @! ~
    5 C7 g: T% w0 [" C
    是不是会快很多？% S6 s2 |% w4 t. T% x! G
    + q& n% @8 S. \# Q/ n: p
    继续扛。
    回复 支持 反对

    使用道具 举报

    qiuwen777
  • TA的每日心情
    开心
    2025-9-3 17:48

    • 签到天数: 595 天

    [LV.9]渡劫
    10#
    发表于 2013-10-7 09:47:11 | 只看该作者
    喜欢喝冰茶 发表于 2013-10-7 09:01
    . T+ l; T1 d, J  ^7 I- z最野蛮也是最简单的办法：一个一个比。

    : Q- i4 _2 c0 N* H: ?- d帮你顶一下。很多问题，看起来很简单，但是在数据量大的情况下，根本不是那么回事。
    / l5 S/ L2 r) v' y9 t4 E这可以产生很多计算机专家。
    4 C* U3 L0 {) B( Z! z对于算法的问题，一般我都躲着。

    点评

    喜欢喝冰茶
    是，一旦数据量很大的时候，计算压力有时是不可容忍的，要不怎么热炒BigData呢。  发表于 2013-10-7 10:36
    回复 支持 反对

    使用道具 举报

    喜欢喝冰茶

    该用户从未签到
    11#
     楼主| 发表于 2013-10-7 10:35:44 | 只看该作者
    本帖最后由 喜欢喝冰茶 于 2013-10-6 20:40 编辑
    3 r% P6 ?8 m1 `/ v. G8 k
    如果两个字符串是这个样子, w" h1 X2 e; W9 ~# J
    ; h2 E3 _" F0 p  o+ Q7 D
    string1: AAAAAATTTTCCCCCGGGTTTTAAAACCCCCCGG2 Q) ~, D$ P4 V: W4 S3 }
    string2: TTAAA
    3 p, u: m! p& f; N: ?/ t8 m
    5 }! P% q, u' h8 {* S% t& J& V
    当然要省很多时间，因为不需要对string1一个一个比了！！！1 u/ a. `# m) n6 M

    3 |" l% D  g9 Z( m  L1 t& mstring1可以写成：7 V# r+ ?/ [$ X: Y; v
    长度 字符 起始位置6 Z2 X* X. C& r, ^
    6      A     19 y5 C) V6 i" Y1 g2 c$ c
    4      T     7
    7 k( G3 H# k; C7 }$ {5      C     11
    # q) D) s0 F. v8 i: i3      G     16
    4 _. f5 C* ]/ v& i" _4      T     19' ~/ V* l. s( e4 [! k3 b
    ......! e" T+ t- W6 G( w
    ! a1 o3 r9 n* F" j, u
    所以当用string2去比的时候，一开始根本就不用考虑字符为A，G，C的行，因为string2开始是T。因此在这个例子中，不需要去检查string1的每个位置，而是非常有限的几个位置，所以可以省很多时间。
      v* t; A6 d: ?4 G$ S& {
    4 h' W& @  `* c& o2 C那么如果存在一种这样的转换方法能够将主贴里的字符串转化成这种，势必会省很多时间。有这样一种方法吗？哪里去找？* D! z  j; B; t! i3 @* n! S

      L0 |; Q" U! X  |7 H7 G; d如果你是有心人，你觉得这个东西最常用在哪里？' E( J- e' g4 y9 q1 d

    ' x6 C: B: @  u对了，文件压缩。
    . a6 H' t% L) O0 L& [# R2 Y
    + P, z# f- L; \1 Q* r, I4 F事实上，真正的解决方法就是借鉴了最早用于文件压缩的一种算法，称为Burrows－Wheeler Transform，又称block-sorting compression。这是当年在DEC工作的Michael Burrows和David Wheeler发明的，所以以他们的名字命名，bzip2的压缩文件就是基于该算法的。它的转换其实很简单，如果感兴趣大家可以google／wiki（wikipedia上很详细的操作细节）上去看细节，但简单的来说，就是把一个字符串头围相接，不停的移动一位，然后排序，最后取出最后一列就行了。Burrows－Wheeler Transform的特性就是转换后的字符串相对于原始字符串含有大量的重复字符片段，所以就可以使得我们的问题变的相对快捷。 : }- a* u/ V1 b+ Q% c+ ^  M
    . t+ }; u( @4 ^" @* o' r6 B8 K" G# d
    那么是否就十全十美，万事大吉了呢？这个需要从实际的具体需求来看。
    $ j; A) z+ G' a' h- B' I; ^
    ( H* |5 m9 _4 r) ?% F扛吧，没什么好说的。- ^4 e: D" Z8 y1 h

    & G1 b* g6 K. i6 p4 n
    回复 支持 反对

    使用道具 举报

    喜欢喝冰茶

    该用户从未签到
    12#
     楼主| 发表于 2013-10-7 10:38:50 | 只看该作者
    MacArthur 发表于 2013-10-6 16:17
    / a$ M2 T& _& E' m( r; i% {这就是基因BLAST算法的标准定义嘛。。。
      n9 p$ ^8 q0 r; ^" o7 I
    - W; z6 q3 e1 W# v: ?3 V3 XGoogle ＂Blast算法＂，一堆开源程序。
    4 e  t- }( M# D) n6 {& m9 W
    blast并非只是解决基因的问题，蛋白同样适用，只不过相对于DNA／RNA而言，蛋白质要复杂得多。
    回复 支持 反对

    使用道具 举报

    MacArthur
  • TA的每日心情
    开心
    2023-3-1 00:08

    • 签到天数: 2397 天

    [LV.Master]无

    13#
    发表于 2013-10-7 11:35:18 | 只看该作者
    喜欢喝冰茶 发表于 2013-10-6 21:38 7 ^; c0 }8 u( d
    blast并非只是解决基因的问题，蛋白同样适用，只不过相对于DNA／RNA而言，蛋白质要复杂得多。 ...
    / f4 J9 {8 D8 g( ~0 p4 r. `
    不明觉厉。。。 上Billion字节的操作，想想就头大。。。 这个规模是不是得上并行计算了？- w$ }: q/ ?8 K4 [5 ^
    回复 支持 反对

    使用道具 举报

    喜欢喝冰茶

    该用户从未签到
    14#
     楼主| 发表于 2013-10-7 11:45:36 | 只看该作者
    MacArthur 发表于 2013-10-6 21:35
    - P: D3 Y* i" l5 U9 Z# ^: T不明觉厉。。。 上Billion字节的操作，想想就头大。。。 这个规模是不是得上并行计算了？, X* y: L7 p) Z
    ...
    # @& p4 |' Z. a9 L7 N- y
    blast好像支持吧，主要不是分布式的问题，而是blast使用的算法对蛋白的分数的定义是很有讲究的，这些分数的定义大概要涉及到另外一个和进化相关的计算领域。
    回复 支持 反对

    使用道具 举报

    老芒
  • TA的每日心情
    奋斗
    2017-3-1 00:54

    • 签到天数: 286 天

    [LV.8]合体
    15#
    发表于 2013-10-7 11:47:04 | 只看该作者
    本帖最后由 老芒 于 2013-10-8 00:21 编辑   Q2 |9 k% l  ]9 I- E
      c0 w/ t3 v0 X) U+ w: w0 j- R
    这样的短贴适合聊天版。

    点评

    橡树村
    这个内容还是很有深度的。  发表于 2013-10-8 00:15
    喜欢喝冰茶
    不明觉厉?什么意思？这能跟paper比吗？只不过为了照顾没基础的同学们了解罢了，例如住院医生。  发表于 2013-10-7 15:13
    老芒
    不明觉厉，但是爱坛不是论文发布地。  发表于 2013-10-7 12:08
    喜欢喝冰茶
    您觉得这个东西很简单？呵呵，最早应用这种方法的文章，已经几乎3千次的引用，虽然是09年发的，另外一篇也有2500次的引用，不乏Science，Nature上的  发表于 2013-10-7 11:58
    回复 支持 反对

    使用道具 举报

    martian
  • TA的每日心情
    开心
    2025-3-30 11:48

    • 签到天数: 1064 天

    [LV.10]大乘
    16#
    发表于 2013-10-7 12:27:10 | 只看该作者
    喜欢喝冰茶 发表于 2013-10-7 10:35 - N2 q& v( p& A, S* ?  v* z* p
    当然要省很多时间，因为不需要对string1一个一个比了！！！
    ' T  c' G8 v; k* J& K! a# R3 V0 ?, \
    string1可以写成：

    7 h7 b+ X) S3 b+ A是要找pattern+ ~! q; t) ~* P

    : Z: ]0 @1 w, i& {  [' Z- H) OEnsembl就用了这种数据压缩方法，- p# {3 A5 m4 m) O6 a# U7 j! o+ z
    AAATTCCGG
    7 C6 X, @& ?6 x" u! ~6 \A3T2C2G2; l1 p+ P* \+ D: k8 @3 e- q

    ; ]& _2 o# d5 u; Q把string1，分成若干片段，多进程查找。

    点评

    喜欢喝冰茶
    呵呵，你这可是托？BWT based的方法是NGS能够大规模应用的基础，也是以后可以做personalize medicine一个很重要的前提，特别是癌症。基于它的程序太有名了  发表于 2013-10-7 15:17
    回复 支持 反对

    使用道具 举报

    喜欢喝冰茶

    该用户从未签到
    17#
     楼主| 发表于 2013-10-7 21:57:48 | 只看该作者
    本帖最后由 喜欢喝冰茶 于 2013-10-7 12:05 编辑 9 e  c) t, W; G( G

    3 x9 v! ?, h8 q" E& R" u已经有同校指出了blast，一个用于对生物大分子的测序程序。这东西正式诞生于1990年，同年人类基因组计划启动。它不仅可以用于DNA/RNA的测序，还可以对蛋白测序。六年前在河里曾经写过一个搭积木的小玩意儿，其中涉及到利用计算方法来预测实验中很难测量的蛋白质空间结构，最有效的计算方法就是同源模型。在这个模型里面，我们允许寻找的字符串,string2可以不用严格的和string1，也就是模板序列，匹配的。换句话说，就是字符串匹配是容错的。具体到主贴里提到的真实问题的挑战，就是模板字符串是人类的基因组（genome），单链长达3billion结构单位，也就是3billion的字符长度，而DNA是双链的，也就是6B的长度。想一想，每个人都是unique的，所以即使都是“健康人”，每个人的基因组都不会完全一样，因此，这种字符串的匹配一定是允许错误的，否则的话，如果大家都一样，即使算法速度再慢都不是问题，因为只做一次，从时间复杂度上，就是0。: R1 T! @* ^/ m, l1 ], D8 }
    8 O$ ]' G5 H1 R7 D2 o3 n1 k
    那么如果考虑容错的匹配，基于bwt方法的算法将面临一个巨大的挑战，因为BWT是严格转换的，可是容错的实际需要，就要考虑转换前和转换后的字符串的错误问题，这会使的问题非常复杂。因此，现在的解决方案就是，当我们需要更多的关注容错的问题时，我们仍然使用传统的，也就是blast所使用的Smith－Waterman算法。具体的细节，感兴趣的可以google／wiki，基本来讲，这是一种被称之为动态编程的计算机算法，可以很好的考虑容错问题，诸如substitution、insertion、deletion或者indel（也就是insertion和deletion的混合体），而这些“错误”，则广泛的存在于病人的基因组中，特别是癌症基因组。当然，现在所使用的smith－waterman基于的方法都是修改了的，主要是计算机算法上的加速，诸如hash的SW算法。9 R3 N( s; R7 U
    # Q) T0 y7 `( C
    但是，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序列的检测成为新生儿的常规检查。
    回复 支持 反对

    使用道具 举报

    喜欢喝冰茶

    该用户从未签到
    18#
     楼主| 发表于 2013-10-9 10:43:40 | 只看该作者
    本帖最后由 喜欢喝冰茶 于 2013-10-10 15:20 编辑
    ' y# x, \9 b3 @, c! Z
    3 P& E# O& K0 A这个帖子里的东西，看起来似乎是一个简单的计算问题，但是却很可能是一场改变人类健康革命的基础。正是由于高速有效的匹配算法的发展，才使得新的测序技术得以广泛应用，不仅是基础研究，而更重要的是临床应用，这里简单的提到一些。等有空的时候，写一些有关基于genome和tanscriptome的技术以及实际应用，像分子诊断技术，这将对癌症的诊断和预期提供巨大的帮助。感兴趣的同学，可以看看AML，也就是急性骨髓性白血病的亚型分类标准，特别是WHO的新标准，还有预期，是否能看懂。* R! _" ~4 B8 u3 t
    回复 支持 反对

    使用道具 举报

    chalet

    该用户从未签到
    19#
    发表于 2013-10-11 12:06:48 | 只看该作者
    喜欢喝冰茶 发表于 2013-10-9 10:43 " ]7 g7 ?" Q6 t7 K4 d* r
    这个帖子里的东西，看起来似乎是一个简单的计算问题，但是却很可能是一场改变人类健康革命的基础。正是由于 ...

    9 {9 ~( I- d$ b欢迎欢迎。6 E' u( b+ S, m% m% t  \0 j9 r
    " r+ S! F+ i7 a8 o# R
    如果说硬要分类，这个应该还是属于生物信息学领域吧，在科教学圃应该很对口啊。4 l% B/ A, [1 H% J

    % h" u8 j/ p9 t使用NCBI网站上的BLAST都是10多年前的事情了，一眨眼人都老了。。。- Q% j$ @# ^$ F$ h" Z

    9 E$ ~3 s7 @/ v8 w; d关于你下面会介绍的内容，非常期待。很久没有学习这方面的知识了，落伍了，亟待补课6 P1 L8 _7 \7 q/ L* H
      q) g' b2 k; D9 z8 W
    回复 支持 反对

    使用道具 举报

    喜欢喝冰茶

    该用户从未签到
    20#
     楼主| 发表于 2013-10-11 23:06:06 | 只看该作者
    chalet 发表于 2013-10-10 22:06
    . {6 {8 w; }4 n欢迎欢迎。/ q0 y" T5 V0 a! h8 H* A8 ^, g: V( b
    ; s5 [7 T, ~; T  J* W3 b) O
    如果说硬要分类，这个应该还是属于生物信息学领域吧，在科教学圃应该很对口啊。
    . r) ^: v( l) C: D# E
    握握手，看起来也是生物计算的啊，现在在做什么？0 T8 I3 G7 R: ]' W6 q

    ( A0 [1 \; F. v还没想好怎么写，涉及的范围得控制一下，要不太大了，而且需要用些篇幅介绍一下疾病得复杂性，像癌症，这个得加好多分子遗传方面的科普，否则的话会很难理解分子诊断方面所面临的挑战。
    & b# s- C3 `3 C/ _! v+ I( q8 R. ^( d0 y! }: T9 |4 H
    昨天刚在八卦里贴了一个，http://www.aswetalk.org/bbs/thread-25733-1-1.html，这是一个很好的分子诊断的例子，并且符合现代医学的发展趋势。以后尽可能的在八卦里发一些小东西，最后写的东西应该都能用的上，慢慢来吧。
    回复 支持 反对

    使用道具 举报

    下一页 »
    12下一页
    返回列表 发新帖

    手机版|小黑屋|Archiver|网站错误报告|爱吱声   

    GMT+8, 2026-1-9 22:49 , Processed in 0.043891 second(s), 18 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

    快速回复 返回顶部 返回列表