Chinaunix

标题: 【问题】对N个相似文本进行计算分析?5000积分求解决~ [打印本页]

作者: huang6894    时间: 2014-08-11 16:01
标题: 【问题】对N个相似文本进行计算分析?5000积分求解决~
本帖最后由 huang6894 于 2014-08-11 17:00 编辑

嗯,因为一些奇葩的需求,想请教一下各位大神~
某目录下有N个以下格式的文本:

1.txt:

  1. Region 1 : chr1 21 33
  2. 0 0 0 0 0 1 1 6 26 26 27 27 28
  3. Region 2 : chr1 73 108
  4. 2 2 2 2 2 3 3 3 3 6 7 7 7 7 7 7 7 7 7 7 19 19 19 19 19 19 19 19 19 19 20 20 20 20 20 21
  5. Region 3 : chr1 109 124
  6. 48 48 48 48 48 48 47 53 53 53 53 53 56 57 55 55
  7. Region 4 : chr1 21 33
  8. 32 44 44 44 44 46 47 47 47 47 47 54 61
  9. Region 5 : chr1 83 99
  10. 26 26 27 27 27 27 28 28 33 33 33 33 33 33 34 34 35
复制代码
2.txt:

  1. Region 1 : chr1 21 33
  2. 1 2 0 4 5 1 1 7 6 6 2 27 28
  3. Region 2 : chr1 73 108
  4. 12 2 2 22 2 23 3 13 13 6 7 7 71 7 6 7 7 7 7 4 19 19 19 19 19 19 19 19 19 19 20 20 20 20 20 21
  5. Region 3 : chr1 109 124
  6. 8 8 8 8 8 8 7 53 53 53 53 53 56 57 55 55
  7. Region 4 : chr1 21 33
  8. 2 44 4 4 4 6 7 7 7 7 7 4 1
  9. Region 5 : chr1 83 99
  10. 6 6 7 7 7 7 8 8 3 3 33 33 33 33 34 34 35
复制代码
他们的单行‘Region ****’都是一样的,但是双行(双行表示region行最后两个数字之间每个点的质量值)是不同的,我现在需要把这N个文件每个点的质量值取平均,每个点的质量值(P)都与这个平均值(Q)做比较,如果P值位于0~0.3Q之间,该点定义为flag1,如果P值位于0.3Q~0.6Q之间,定义改点为flag2,否则为flag3.(不会啊~)

最难的是:只有在一个区域(最少连续5个点)中有60%(3个)以上相同的flag时,认为该flag可信,输出这个区域和flag,如chr1 2-6  flag1
----------------------------------------------

编辑一下:举个例子:

-----------------------------
比如我们有4个文件都是题目的格式,然后:
在于Region 2 : chr1 73 108上,表示73到77这5bp的质量分别是:
1.txt:

1 1 1 1 1

2.txt:

2 2 2 2 2

3.txt:

3 3 3 3 3

4.txt:

4 4 4 4 4

-------------------------
那么每个点的平均质量值应该是:
2.5 2.5 2.5 2.5 2.5
--------------------------------------
那么对比条件:每个点的质量值(P)都与这个平均值(Q)做比较,如果P值位于0~0.3Q之间,该点定义为flag1,如果P值位于0.3Q~0.6Q之间,定义改点为flag2,否则为flag3.
----------------------------------------------------------------
应该是:
1.txt:

flag2 flag2 flag2 flag2 flag2


2.txt:

flag3 flag3 flag3 flag3 flag3

3.txt:

flag3 flag3 flag3 flag3 flag3

4.txt:

flag3 flag3 flag3 flag3 flag3
-------------------------------------
于是我们得到结果是:
1.txt    chr1  73-77  flag2
2.txt    chr1  73-77  flag3
3.txt    chr1  73-77  flag3
4.txt    chr1  73-77  flag3

---------------------------------------------------
上面举的例子是很特殊的,一般的例子可能是:

同样四个文本:
chr1 1-11
对比条件后是:
1.txt:

flag2 flag1 flag2 flag2 flag2  flag1  flag3  flag3  flag3   flag3  flag3  


2.txt:

flag3 flag3 flag3 flag2 flag2  flag2  flag2  flag3  flag3   flag3  flag3  #1-5:flag3===6-11:flag3(4-8:flag2 ?)===>优先判断为flag1,然后是flag2,最后才是flag3,也就是说我们需要首先认同4-8是flag2,然后再认为1-3是flag3,9-11是flag3

3.txt:

flag3 flag1 flag3 flag1 flag1  flag3  flag1  flag1  flag1   flag1  flag1  

4.txt:

flag3 flag3 flag3 flag3 flag3  flag3  flag3  flag3  flag3   flag3  flag3  
-------------------------------------
于是我们得到结果是:
1.txt    chr1  1-5  flag2
1.txt    chr1  6-11  flag3
2.txt    chr1  1-3  flag3
2.txt    chr1  4-8  flag2
2.txt    chr1  9-11  flag3
3.txt    chr1  1-11  flag1
3.txt    chr1  1-11  flag3
---------------------------------------------------
说实话,我一个人研究,估计一年也搞不出来。。。。只能跪求各位大神了。。。。。

作者: pitonas    时间: 2014-08-11 16:01
本帖最后由 pitonas 于 2014-08-16 05:32 编辑

这个问题, 我不放弃 ~ {:2_172:}
基本完成
~ {:2_168:}
  1. #!/usr/bin/perl -w
  2. use 5.010;

  3. my @txt = qw/1.txt 2.txt/;          # glob or ...
  4. my @tmp = map { "$_.tmp" } @txt;    # tmp files
  5. my ( $fh, @fh ) = map { open my $f, '<', $_; $f } @txt;
  6. my @write_fh    = map { open my $f, '>', $_; $f } @tmp;
  7. my ( $CHR, $BEGIN );

  8. while (<$fh>) {
  9.     ( $CHR, $BEGIN ) = (split)[ 3, 4 ];
  10.     my @pos   = [ split /\s/, <$fh> ];
  11.     my $index = $#{ $pos[0] };

  12.     for my $f (@fh) {
  13.         readline $f;
  14.         push @pos, [ split /\s/, <$f> ];
  15.     }

  16.     my @ave = map {
  17.         my ( $i, $sum ) = $_;
  18.         $sum += $pos[$_][$i] for 0 .. $#pos;
  19.         $sum / @pos;
  20.     } 0 .. $#{ $pos[0] };

  21.     for my $i ( 0 .. $#pos ) {
  22.         my @flag = map {
  23.             my $F = $pos[$i][$_] / ( $ave[$_] || 1 );
  24.             [ $F = $F <= 0.3 ? 0 : $F > 0.6 ? 2 : 1, 1 ];
  25.         } 0 .. $index;

  26.         separate( $i, @flag );
  27.     }
  28. }

  29. sub separate {
  30.     my $index = shift;
  31.     my @flag = ( [], [], [] );

  32.     for my $f ( 1 .. 3 ) {
  33.         for ( my $i = 0 ; $i <= $#_ - 4 ; $i++ ) {
  34.             next if $_[$i][0] ne $f;
  35.             $i += 7 and next if !$_[ $i + 2 ][1];
  36.             my $end  = $i + 4;
  37.             my $zero = 0;
  38.             for my $x ( reverse $end - 1 .. $end ) {
  39.                 $_[$x][1] ? last : $zero++;
  40.             }

  41.             my $count = grep { $_[$_][0] == $f } $i .. $end - $zero;
  42.             next if $count < 3;
  43.             @{ $_[$_] } = ( $f, 0 ) for $i .. $end - $zero;
  44.             $i += 4 + $zero ? 5 - $zero : 0;
  45.         }
  46.     }

  47.     for my $i ( 0 .. $#_ ) {
  48.         !$flag[ $_[$i][0] ][0] || ( $i - $flag[ $_[$i][0] ][-1][-1] != 1 )
  49.           ? push @{ $flag[ $_[$i][0] ] }, [$i]
  50.           : ( $flag[ $_[$i][0] ][-1][1] = $i );
  51.     }
  52.     my $i;
  53.     for my $f (@flag) {
  54.         $i++;
  55.         for my $range (@$f) {
  56.             @$range <= 1 || $range->[1] - $range->[0] < 2 and next;
  57.             my $range = join '-', map { $_ + $BEGIN } @$range;
  58.             say { $write_fh[$index] } "$txt[$index]\t$CHR\t$range\tf$i";
  59.         }
  60.     }
  61. }

  62. close $_ for @write_fh;
  63. `cat @tmp > result.txt`;    # cat

  64. __DATA__
  65.     ~ 0.3
  66. 0.3 ~ 0.6
  67. 0.6 ~
复制代码

作者: q1208c    时间: 2014-08-11 16:18
没看明白你说的具体意思, 能不能手工写一下你要的结果是什么样的?

另外, 你的双行数据这么多, 全是 质量 么? 有的还是一串0 ...
作者: pitonas    时间: 2014-08-11 16:21
my $师傅 jason680:
  1. 问题本不难,你又不举例,
  2. 描述又乱写,让人费疑猜?
复制代码
难的不是问题 ~ {:2_172:}
最难的是看懂问题 ~ {:2_168:}
作者: xiumu2280    时间: 2014-08-11 16:24
本帖最后由 xiumu2280 于 2014-08-11 16:27 编辑

生信的表示看懂了
作者: xiumu2280    时间: 2014-08-11 16:31
本帖最后由 xiumu2280 于 2014-08-11 16:31 编辑

他们的单行‘Region ****’都是一样的, #两行为一个单位,第一行相当于一个ID,chr1 21 33,表示在chr1上21到33的位置,下面第二行是对应在21到33位置上碱基的质量值也就是每个点的P值。
但是双行(双行表示region行最后两个数字之间每个点的质量值)是不同的,
我现在需要把这N个文件每个点的质量值取平均, #按照位置在多个文件内来个交叉求和再算平均值,这个平均值就是Q值。
每个点的质量值(P)都与这个平均值(Q)做比较, #即用P/Q
如果P值位于0~0.3Q之间,该点定义为flag1,如果P值位于0.3Q~0.6Q之间,定义改点为flag2,否则为flag3.(不会啊~)

最难的是:只有在连续5个点中有3个以上相同的flag时,认为该flag可信, #就是连续的5个位置中有3个以上在相同的flag区域,则输出该区域
输出这5个点的区域和flag,如chr1 2-6  flag1

我来帮你解释一下回复 3# pitonas


   
作者: huang6894    时间: 2014-08-11 16:32
本帖最后由 huang6894 于 2014-08-11 16:39 编辑

@q1208c@pitonas两位大神,我很抱歉啊~
比如我们有4个文件都是题目的格式,然后:
在于Region 2 : chr1 73 108上,表示73到77这5bp的质量分别是:
1.txt:

1 1 1 1 1

2.txt:

2 2 2 2 2

3.txt:

3 3 3 3 3

4.txt:

4 4 4 4 4

-------------------------
那么每个点的平均质量值应该是:
2.5 2.5 2.5 2.5 2.5
--------------------------------------
那么对比条件:每个点的质量值(P)都与这个平均值(Q)做比较,如果P值位于0~0.3Q之间,该点定义为flag1,如果P值位于0.3Q~0.6Q之间,定义改点为flag2,否则为flag3.
----------------------------------------------------------------
应该是:
1.txt:

flag2 flag2 flag2 flag2 flag2


2.txt:

flag3 flag3 flag3 flag3 flag3

3.txt:

flag3 flag3 flag3 flag3 flag3

4.txt:

flag3 flag3 flag3 flag3 flag3
-------------------------------------
于是我们得到结果是:
1.txt    chr1  73-77  flag2
2.txt    chr1  73-77  flag3
3.txt    chr1  73-77  flag3
4.txt    chr1  73-77  flag3

作者: huang6894    时间: 2014-08-11 16:34
回复 5# xiumu2280


    xiumu2280大神我爱死你了~{:2_178:}

-----------------------
各位大神请原谅一个体育老师教语文的孩子~
作者: xiumu2280    时间: 2014-08-11 16:35
能看懂问题,我感到很开心 {:2_168:} 回复 7# huang6894


   
作者: xiumu2280    时间: 2014-08-11 16:49
想了一下,哈希切片简直就是为这个问题准备的·····
看看晚上帮你写下回复 7# huang6894


   
作者: huang6894    时间: 2014-08-11 16:52
回复 2# q1208c


    0是有可能的,就上面举的例子是很特殊的,一般的例子可能是:

同样四个文本:
chr1 1-11
对比条件后是:
1.txt:

flag2 flag1 flag2 flag2 flag2  flag1  flag3  flag3  flag3   flag3  flag3  


2.txt:

flag3 flag3 flag3 flag2 flag2  flag2  flag2  flag3  flag3   flag3  flag3  #1-5:flag3===6-11:flag3(4-8:flag2 ?)===>优先判断为flag1,然后是flag2,最后才是flag3,也就是说我们需要首先认同4-8是flag2,然后再认为1-3是flag3,9-11是flag3

3.txt:

flag3 flag1 flag3 flag1 flag1  flag3  flag1  flag1  flag1   flag1  flag1  

4.txt:

flag3 flag3 flag3 flag3 flag3  flag3  flag3  flag3  flag3   flag3  flag3  
-------------------------------------
于是我们得到结果是:
1.txt    chr1  1-5  flag2
1.txt    chr1  6-11  flag3
2.txt    chr1  1-3  flag3
2.txt    chr1  4-8  flag2
2.txt    chr1  9-11  flag3
3.txt    chr1  1-11  flag1
3.txt    chr1  1-11  flag3
---------------------------------------------------
说实话,我一个人研究,估计一年也搞不出来。。。。只能跪求各位大神了。。。。。
作者: huang6894    时间: 2014-08-11 16:54
回复 9# xiumu2280


    谢谢xiumu大哥~哈希切片还是第一次听说,我也去补充一下这方面的知识,谢谢你谢谢~
作者: pitonas    时间: 2014-08-11 17:15
谢谢 $师傅解释一下 ~{:2_172:}

回复 5# xiumu2280


   
作者: pitonas    时间: 2014-08-11 19:40
说实话,我估计看一年也看不懂问题 ~ {:2_176:}

3.txt:
flag3 flag1 flag3 flag1 flag1  flag3  flag1  flag1  flag1   flag1  flag1  

得到结果是:{:2_170:}
3.txt    chr1  1-11  flag1
3.txt    chr1  1-11  flag3


LZ 帮解释一下 what + why ?

A:
f1 f2 f1 f2 f1 f2 f1 f2 f3 f2 f3 f3 f1
B:
f1 f1 f2 f1 f1 f1 f2 f2 f1

得到结果是? and how ?

作者: xiumu2280    时间: 2014-08-11 20:42
不是5个一组嘛  
3.txt    chr1  1-11  flag1
3.txt    chr1  1-11  flag3
又是什么意思
作者: chenhao392    时间: 2014-08-11 23:11
bioinfo的表示看懂了,会写,但是没空....
NGS的数据处理,我表示我最关心文件大小....
你的这些文件多大?你的电脑内存多大?

硬件可以的话直接hash,不行的话就分步处理了。
另,LZ考虑看一些BEDtools,应该有用。https://code.google.com/p/bedtools/

To 其他Perler,此种文件一般动辄上Gb,多个文件,我担心Perl的Hash会吃掉很多内存。
作者: yestreenstars    时间: 2014-08-12 00:35
土豪出手就是阔绰!
作者: chenhao392    时间: 2014-08-12 05:02
给个思路,LZ自己写写代码看看吧... 然后,此思路有用的假设是,你机器内存不足....

1. 将两行变一行,\t 分割。 chr1   1   100    11,22,33,44,55
2. 然后sort -k1 -k2n
4. Loop:
          a. 定义一个sliding window. 例如: chr1:1-10000
          b. 对于每一个文件,只读入一部分reads (sliding window定义范围),建立若干工作hash
              做你需要的per base 的统计,输出flag
                 i. 确保所有的相关reads都被读入了。
                    在这里,Loop 第一次为向下查到起始位置为10001, 因为sort了,之后的不用查了...
                 ii. 你需要一个hash of array
                     key: position, such as: chr1:100
                     value: array of quality values
                 iii. 因为每一个read有长度的限制,两个sliding window 之间的overlap只需要是这个长度就好..
                      这样会产生一定的冗余,但是输出stats该是一样的。计算速度该是可以接受的.
          c. 删除工作hash..
5. 将step 4的输出结果去冗余.

作者: huang6894    时间: 2014-08-12 06:11
回复 14# xiumu2280


    是五个一组,不过,每组得到结果合并了
作者: huang6894    时间: 2014-08-12 06:19
回复 13# pitonas


    对不起~我也很纠结啊~
A:
f1 f2 f1 f2 f1 f2 f1 f2 f3 f2 f3 f3 f1
B:
f1 f1 f2 f1 f1 f1 f2 f2 f1

得到结果是:首先a前五个得到f16-10得到f2后面的如果是有三个以上f3的话定义为f3.或者有f2紧跟着6-10的话该点并到6—10区域~
b前五个得到f1由于六七也是f1所以1—7归为f 1,剩下的三个得看后面了
作者: huang6894    时间: 2014-08-12 06:20
回复 15# chenhao392


    文件倒是挺小的,一个也就1M,大概50个的样子
作者: huang6894    时间: 2014-08-12 06:22
回复 17# chenhao392


    遇到生信大神了,这很像之前看到的某文章提到的算法诶,谢谢,谢谢
作者: huang6894    时间: 2014-08-12 06:23
回复 16# yestreenstars


    这……呵呵,呵呵呵~~
作者: huang6894    时间: 2014-08-12 06:43
各位大神,第一问,我好像能实现诶~主要是第二问:只有在一个区域(最少连续5个点)中有60%(3个)以上相同的flag时,认为该flag可信,输出这个区域和flag,如chr1 2-6  flag1

能不能这样,我把每个点做比较后的结果进行分别赋值,比如flag1是1,flag2是2.flag3是4,然后对每个连续的点进行加运算,问题是,有没有相关的方法支持判断N个数平均值是否在某指定范围,若果是,继续和下一个点相加求平均再判断~如此类推……
好像不太行………
我去试试,&#128513;
作者: ly5066113    时间: 2014-08-12 08:58
回复 23# huang6894


盖了这么多楼,1楼的2个原始文本想得到的结果都没有。

计算均值 和 Region 有没有关系?
同一个文本中明显有区间重叠的,怎么算?
Region 1 : chr1 21 33
Region 4 : chr1 21 33
作者: huang6894    时间: 2014-08-12 09:15
回复 24# ly5066113


    嘿嘿~抱歉抱歉,我不是故意的~
----------------------------------------------
区域不会有重叠,每个区域实际上会相距几百个单位以上~抱歉了抱歉了~
作者: ly5066113    时间: 2014-08-12 09:47
回复 25# huang6894


最少连续5个点,也就是5个及5个以上,当发生冲突的时候,怎么处理?

flag1 flag1 flag2 flag2 flag1 flag2 flag2

1-5 是 flag1
2-7 是 flag2

优先 2-7 的?


flag1 flag1 flag2 flag2 flag1 flag2

1-5 是 flag1
2-6 是 flag2

又以哪个为准?
作者: afukada    时间: 2014-08-12 10:47
3.txt:

flag3 flag1 flag3 flag1 flag1  flag3  flag1  flag1  flag1   flag1  flag1  

4.txt:

flag3 flag3 flag3 flag3 flag3  flag3  flag3  flag3  flag3   flag3  flag3  

根據規則

3.txt    chr1  1-11  flag1
3.txt    chr1  1-11  flag3

這兩行結果是不是你打錯了

實際上是

3.txt    chr1  1-11  flag1
4.txt    chr1  1-11  flag3
作者: huang6894    时间: 2014-08-12 11:34
回复 26# ly5066113


    按照优先级,首先flag1
作者: huang6894    时间: 2014-08-12 11:35
回复 27# afukada


    是的,-_-#,楼主不但语文不好而且还粗心
作者: afukada    时间: 2014-08-12 12:04
看起來可以使用dynamic programming

以這個例子為例

flag3 flag1 flag3 flag1 flag1  flag3  flag1  flag1  flag1   flag1  flag1

共有11個點

     1 2 3 4 5 6 7 起始位置
5   1
6   0 1
7   0 1 1
8   1 1 1 1
9   1 1 1 1 1
10 1 1 1 1 1 1
11 1 1 1 1 1 1 1





最上面那一列是起始位置(從1-7, 因為題目條件至少要5個點, 所以最末端就是7-11)
最左邊那一排是終止位置(從5-11, 因為題目條件至少要5個點, 所以最前端就是1-5)

表裡面的數字代表是哪個flag(flag1-flag3, 0表示沒有flag)
所以可以得到這張表只有一個flag的可能性
就是flag1
取其最長長度
就是1-11
所以可以得到
1-11 flag1

驗證一下

flag3 flag3 flag3 flag2 flag2  flag2  flag2  flag3  flag3   flag3  flag3

     1 2 3 4 5 6 7 起始位置
5   3
6   0 2
7   0 2 2
8   3 0 2 2
9   3 0 0 2 2
10 3 0 0 0 0 3
11 3 3 0 0 0 3 3





可以得到這張表有兩個flag的可能性
就是flag2和flag3
其中flag2的priority較高
所以取其最長長度2-7, 3-8, 4-9
這邊就...

所以是不是還需要考慮其他原因
比方說還要比例最高(因為照你題目敘述, 4-8是所有組合裡面flag2的比例最高)
作者: huang6894    时间: 2014-08-12 12:25
回复 30# afukada


    (⊙0⊙)。。。流弊!!!
作者: 大山里出来的孩子    时间: 2014-08-12 13:30
  O(∩_∩)O~回复 3# pitonas


   
作者: xiumu2280    时间: 2014-08-12 14:26
昨天看的解释,和今天看的解释,完全是2种不同的情况。
作者: yinyuemi    时间: 2014-08-12 15:13
回复 1# huang6894


    如果是你给的数据应该输出啥?
作者: huang6894    时间: 2014-08-12 15:33
回复 33# xiumu2280


    {:2_166:} 。。。我错了,对不起
作者: huang6894    时间: 2014-08-12 15:34
回复 34# yinyuemi


    {:2_175:} 我想还是放弃吧。。。太麻烦了。。。
作者: pitonas    时间: 2014-08-12 17:56
给一些复杂的例子, 并解释 ~ {:2_171:}
你的规则 ?

my $question; ~ {:2_168:}

3 3 3 2 2 1 1 1 2 3

1 > 3

1:
2 2 1 1 1 => F1: 4-8
3 3 3 => F3: 1-3


or
2:

1 1 1 2 3 => F1: 6-10
3 3 3 2 2 => F3: 1-5

or ....




example 2.txt

flag3 flag3 flag3 flag2 flag2  flag2  flag2  flag3  flag3   flag3  flag3

f2 > f3

1:
flag3 flag3 flag2 flag2  flag2 => F2: 2-6
flag2  flag3  flag3   flag3  flag3 => F3: 7-11

2:
flag2 flag2  flag2  flag2  flag3 => F2: 4-8
flag3 flag3 flag3 => F3: 1-3
flag3   flag3  flag3 => 9-11

3:
flag3 flag2 flag2  flag2  flag2 => F2: 3-7
flag3  flag3   flag3  flag3 => F3: 8-11

or....
作者: huang6894    时间: 2014-08-12 21:05
回复 37# pitonas


    实际上。。。很少会遇到这么复杂的情况的。。。不过正如大神的例子:
3 3 3 2 2 1 1 1 2 3,根据1>2>3,理论应该是:
1 1 1 2 3 => F1: 6-10
3 3 3 2 2 => F3: 1-5

flag3 flag3 flag3 flag2 flag2  flag2  flag2  flag3  flag3   flag3  flag3
应该是:

flag2 flag2  flag2  flag2  flag3 => F2: 4-8
flag3 flag3 flag3 => F3: 1-3
flag3   flag3  flag3 => 9-11

----------------------
好吧,我自己都晕了。。。还是果断放弃的好~

作者: huang6894    时间: 2014-08-13 10:53
回复 2# pitonas


    大神, 快粗来让我膜拜一下。。。。太流弊了!!!!
作者: pitonas    时间: 2014-08-13 11:01
哪里是我的帖子? 我找不到 ?  {:2_167:}

回复 40# huang6894


   
作者: huang6894    时间: 2014-08-13 12:16
回复 41# pitonas


    已被选为最佳答案





欢迎光临 Chinaunix (http://bbs.chinaunix.net/) Powered by Discuz! X3.2