求有多少种匹配的可能 [组合 (非排列)]

substr函数

有一个DNA序列，

ACGUAGCU

A和U，C和G匹配，但是中间不能有交叉，

AU AU 不能有交叉
AU CG 不能有交叉
CG CG 不能有交叉

交叉:

比如 [1, 5], [3, 8]  1  3  5  8

不交叉:

比如 [1, 3], [4, 8]  1  3  4  8
比如 [1, 8], [3, 5]  1  3  5  8


比如第二位 C 和第六位 G 不能匹配:
因为他俩要是匹配，第三位 G 必定只能跟第七位 C 匹配，[2, 6], [3, 7] 这样的话就有交叉。

所以这个序列只有两种匹配方式，

dna = 'ACGUAGCU'
[A|U]  [G|C]

[ [ 1, 4 ], [ 5, 8 ] ]        [ [ 2, 3 ], [ 6, 7 ] ]
[ [ 1, 8 ], [ 4, 5 ] ]        [ [ 2, 3 ], [ 6, 7 ] ]

COUNT = 2

第一位A和第四位U,第二位C和第三位G,第五位A和第八位U,第六位G和第七位C。
或者第一位A和第八位U,第四位U和第五位A,第二位C和第三位G,第六位G和第七位C匹配。

求有多少种匹配的可能 [组合 (非排列)]，

求大神  优化 算法。

实际的序列有比如

dna = 'ACGUAGCUACGUAGCUACGUAGCUACGUAGCUACGUAGCUACGUAGCUACGUAGCUACGUAGCUACGUAGCU'

或长更多


原来的问题来自
http://bbs.chinaunix.net/thread-4186719-1-1.html

sunzhiguolu

这个问题实在有点深奥,不懂. 站脚助威!

ly5066113

回复 1# substr函数


[ 1, 8 ], [ 4, 5 ]

为什么不算交叉？

tuyajie

300PB.......这个不是算法层面优化的事情了感觉。。。

substr函数

回复 3# ly5066113

大神 是这样的
交叉

比如 [1, 5], [3, 8]  1  3  5  8

1 内 1 外  算交叉
1 ==> [3, 8] 外
5 ==> [3, 8] 内

不交叉:

[ 1, 8 ], [ 4, 5 ] => 2 外 [或 2 内]
1 ==> [4, 5] 外
8 ==> [4, 5] 外


   

substr函数

回复 2# sunzhiguolu


谢谢 站脚助威

substr函数

回复 4# tuyajie
T 神
len(dna) => 100
假设是长度 100 好了

ly5066113

回复 4# tuyajie


是 300bp

中文名称：碱基对
英文名称：base pair;bp

tuyajie

好吧。好专业的。我去写写看回复 8# ly5066113


   

jason680

回复 1# substr函数

有想法/算法，才有代码...

dna = 'ACGUAGCU'
AU,CG分组
AU => AUAU
CG => CGGC     

简单(AU,CG)组合匹配是容易的......
AUAU =>  AUAU, AUAU
CGGC => CGGC,  CGGC(交叉匹配)

要 优化 符合(不可交叉)条件匹配...
就要费心找出想法/算法...

设权数 A = +1(记号: p), U = -1(记号: n)
AUAU
pnpn   <==权数(p=+1, n=-1)
NNNN  <==使用(Y=Yes/Used, N=No/No Use)

设权数 C = +1(记号:p), G = -1(记号: n)
CGGC
pnnp   <==权数(p=+1, n=-1)
NNNN  <==使用(Y=Yes/Used, N=No/No Use)

递归 匹配
a: 找到第一个 未使用AU(或CG)
  记录 使用(Y),且设该位置为S点(start开始点)
例:
AUAU
pnpn   <==权数(p=+1, n=-1)
YNNN  <==使用(Y=Yes/Used, N=No/No Use)
S

b: 向后(向右) 找AU(或CG)匹配 E点(结束点)
AU匹配条件: S到E权数和= 0, 且S,E为匹配AU或UA(权数和=0) 不可为AA(权数和+2)或UU(权数和-2)
CG匹配条件: S到E权数和= 0, 且S,E为匹配GC或CG(权数和=0) 不可为CC(权数和+2)或GG(权数和-2)
  S到E权数和= 0, 为 算法 优化 重点...


匹配成功, 例： -------------------------------------------------
AUAU
pnpn   <==权数(p=+1, n=-1)
YYNN  <==使用(Y=Yes/Used, N=No/No Use)
SE
AU匹配(权数匹配p,n = +1,-1 = 0)
S到E权数和 = p,n = +1,-1 = 0,

匹配(一组)完成，设定 E点为使用(Y)
调用下一个递归......直到全部（未使用N）匹配成功

匹配失败，例： -------------------------------------------
CGGC => CGGC,  CGGC(交叉匹配)

第一次CG匹配成功
CGGC
pnnp   <==权数(p=+1, n=-1)
YYNN  <==使用(Y=Yes/Used, N=No/No Use)
SE
CG匹配(权数匹配p,n = +1,-1 = 0)
S到E权数和 = p,n = +1,-1 = 0,
匹配(一组)完成，设定 E点为使用(Y)
调用下一个递归......直到全部（未使用N）匹配成功

第二次CG匹配失败（优化重点 - 排除交叉匹配）
CGGC
pnnp   <==权数(p=+1, n=-1)
YNNN  <==使用(Y=Yes/Used, N=No/No Use)
S_E
CG(权数和 0)虽是匹配....
S到E权数和 = p,n,n = +1,-1,-1 = -1 (非交叉匹配检查：失败)

第三次CG匹配失败（CC匹配）
CGGC
pnnp   <==权数(p=+1, n=-1)
YNNN  <==使用(Y=Yes/Used, N=No/No Use)
S__E
CC(权数和+2) 匹配检查：失败
S到E权数和 = p,n,n,p = +1,-1,-1,+1 = 0

CGGC匹配结束（只有一次匹配成功）

---------------------------------------------------------------------------------------

1. --- 0000000001111111
   
2. --- 1234567890123456
   
3. in: ACGUAGCUACGUAGCU
   
4. AU: A  UA  UA  UA  U
   
5. CG:  CG  GC  CG  GC
   
6. Pos: A(1) U(4) A(5) U(8) A(9) U(12) A(13) U(16)
   
7. Pos: C(2) G(3) G(6) C(7) C(10) G(11) G(14) C(15)
   
8. 1: [  [1,4], [5,8], [9,12], [13,16] ]
   
9. 2: [  [1,4], [5,8], [9,16], [12,13] ]
   
10. 3: [  [1,4], [5,12], [8,9], [13,16] ]
    
11. 4: [  [1,4], [5,16], [8,9], [12,13] ]
    
12. 5: [  [1,4], [5,16], [8,13], [9,12] ]
    
13. 6: [  [1,8], [4,5], [9,12], [13,16] ]
    
14. 7: [  [1,8], [4,5], [9,16], [12,13] ]
    
15. 8: [  [1,12], [4,5], [8,9], [13,16] ]
    
16. 9: [  [1,12], [4,9], [5,8], [13,16] ]
    
17. 10: [  [1,16], [4,5], [8,9], [12,13] ]
    
18. 11: [  [1,16], [4,5], [8,13], [9,12] ]
    
19. 12: [  [1,16], [4,9], [5,8], [12,13] ]
    
20. 13: [  [1,16], [4,13], [5,8], [9,12] ]
    
21. 14: [  [1,16], [4,13], [5,12], [8,9] ]
    
22. AU count: 14
    
23. 1: [  [2,3], [6,7], [10,11], [14,15] ]
    
24. 2: [  [2,3], [6,15], [7,14], [10,11] ]
    
25. 3: [  [2,11], [3,10], [6,7], [14,15] ]
    
26. CG count: 3
    
27. Total count: 42

复制代码