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

substr函數(shù)

有一個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匹配。

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

求大神  優(yōu)化 算法。

實際的序列有比如

dna = 'ACGUAGCUACGUAGCUACGUAGCUACGUAGCUACGUAGCUACGUAGCUACGUAGCUACGUAGCUACGUAGCU'

或長更多


原來的問題來自
http://www.72891.cn/thread-4186719-1-1.html

sunzhiguolu

這個問題實在有點深奧,不懂. 站腳助威!

ly5066113

回復(fù) 1# substr函數(shù)


[ 1, 8 ], [ 4, 5 ]

為什么不算交叉？

tuyajie

300PB.......這個不是算法層面優(yōu)化的事情了感覺。。。

substr函數(shù)

回復(fù) 3# ly5066113

大神 是這樣的
交叉

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

1 內(nèi) 1 外  算交叉
1 ==> [3, 8] 外
5 ==> [3, 8] 內(nèi)

不交叉:

[ 1, 8 ], [ 4, 5 ] => 2 外 [或 2 內(nèi)]
1 ==> [4, 5] 外
8 ==> [4, 5] 外


   

substr函數(shù)

回復(fù) 2# sunzhiguolu


謝謝 站腳助威

substr函數(shù)

回復(fù) 4# tuyajie
T 神
len(dna) => 100
假設(shè)是長度 100 好了

ly5066113

回復(fù) 4# tuyajie


是 300bp

中文名稱：堿基對
英文名稱：base pair;bp

tuyajie

好吧。好專業(yè)的。我去寫寫看回復(fù) 8# ly5066113


   

jason680

回復(fù) 1# substr函數(shù)

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

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

簡單(AU,CG)組合匹配是容易的......
AUAU =>  AUAU, AUAU
CGGC => CGGC,  CGGC(交叉匹配)

要 優(yōu)化 符合(不可交叉)條件匹配...
就要費心找出想法/算法...

設(shè)權(quán)數(shù) A = +1(記號: p), U = -1(記號: n)
AUAU
pnpn   <==權(quán)數(shù)(p=+1, n=-1)
NNNN  <==使用(Y=Yes/Used, N=No/No Use)

設(shè)權(quán)數(shù) C = +1(記號:p), G = -1(記號: n)
CGGC
pnnp   <==權(quán)數(shù)(p=+1, n=-1)
NNNN  <==使用(Y=Yes/Used, N=No/No Use)

遞歸 匹配
a: 找到第一個 未使用AU(或CG)
  記錄 使用(Y),且設(shè)該位置為S點(start開始點)
例:
AUAU
pnpn   <==權(quán)數(shù)(p=+1, n=-1)
YNNN  <==使用(Y=Yes/Used, N=No/No Use)
S

b: 向后(向右) 找AU(或CG)匹配 E點(結(jié)束點)
AU匹配條件: S到E權(quán)數(shù)和= 0, 且S,E為匹配AU或UA(權(quán)數(shù)和=0) 不可為AA(權(quán)數(shù)和+2)或UU(權(quán)數(shù)和-2)
CG匹配條件: S到E權(quán)數(shù)和= 0, 且S,E為匹配GC或CG(權(quán)數(shù)和=0) 不可為CC(權(quán)數(shù)和+2)或GG(權(quán)數(shù)和-2)
  S到E權(quán)數(shù)和= 0, 為 算法 優(yōu)化 重點...


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

匹配(一組)完成，設(shè)定 E點為使用(Y)
調(diào)用下一個遞歸......直到全部（未使用N）匹配成功

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

第一次CG匹配成功
CGGC
pnnp   <==權(quán)數(shù)(p=+1, n=-1)
YYNN  <==使用(Y=Yes/Used, N=No/No Use)
SE
CG匹配(權(quán)數(shù)匹配p,n = +1,-1 = 0)
S到E權(quán)數(shù)和 = p,n = +1,-1 = 0,
匹配(一組)完成，設(shè)定 E點為使用(Y)
調(diào)用下一個遞歸......直到全部（未使用N）匹配成功

第二次CG匹配失�。�優(yōu)化重點 - 排除交叉匹配）
CGGC
pnnp   <==權(quán)數(shù)(p=+1, n=-1)
YNNN  <==使用(Y=Yes/Used, N=No/No Use)
S_E
CG(權(quán)數(shù)和 0)雖是匹配....
S到E權(quán)數(shù)和 = p,n,n = +1,-1,-1 = -1 (非交叉匹配檢查：失敗)

第三次CG匹配失�。–C匹配）
CGGC
pnnp   <==權(quán)數(shù)(p=+1, n=-1)
YNNN  <==使用(Y=Yes/Used, N=No/No Use)
S__E
CC(權(quán)數(shù)和+2) 匹配檢查：失敗
S到E權(quán)數(shù)和 = p,n,n,p = +1,-1,-1,+1 = 0

CGGC匹配結(jié)束（只有一次匹配成功）

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

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

復(fù)制代碼