免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
查看: 1785 | 回复: 9

[数值计算] 求有多少种匹配的可能 [组合 (非排列)] [复制链接]

论坛徽章:
26
2015亚冠之胡齐斯坦钢铁
日期:2015-06-25 21:40:202015亚冠之柏斯波利斯
日期:2015-08-31 17:03:192015亚冠之柏斯波利斯
日期:2015-11-07 13:10:00程序设计版块每日发帖之星
日期:2015-11-10 06:20:00每日论坛发贴之星
日期:2015-11-10 06:20:00程序设计版块每日发帖之星
日期:2015-11-26 06:20:00程序设计版块每日发帖之星
日期:2015-12-02 06:20:00黄金圣斗士
日期:2015-12-07 17:57:4615-16赛季CBA联赛之天津
日期:2015-12-23 18:34:14程序设计版块每日发帖之星
日期:2016-01-02 06:20:00程序设计版块每日发帖之星
日期:2016-01-06 06:20:00每日论坛发贴之星
日期:2016-01-06 06:20:00
发表于 2015-08-31 20:20 |显示全部楼层
有一个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

论坛徽章:
307
程序设计版块每周发帖之星
日期:2016-04-08 00:41:33操作系统版块每日发帖之星
日期:2015-09-02 06:20:00每日论坛发贴之星
日期:2015-09-02 06:20:00程序设计版块每日发帖之星
日期:2015-09-04 06:20:00每日论坛发贴之星
日期:2015-09-04 06:20:00每周论坛发贴之星
日期:2015-09-06 22:22:00程序设计版块每日发帖之星
日期:2015-09-09 06:20:00程序设计版块每日发帖之星
日期:2015-09-19 06:20:00程序设计版块每日发帖之星
日期:2015-09-20 06:20:00每日论坛发贴之星
日期:2015-09-20 06:20:00程序设计版块每日发帖之星
日期:2015-09-22 06:20:00程序设计版块每日发帖之星
日期:2015-09-24 06:20:00
发表于 2015-08-31 22:48 |显示全部楼层
这个问题实在有点深奥,不懂. 站脚助威!

论坛徽章:
23
15-16赛季CBA联赛之吉林
日期:2017-12-21 16:39:27白羊座
日期:2014-10-27 11:14:37申猴
日期:2014-10-23 08:36:23金牛座
日期:2014-09-30 08:26:49午马
日期:2014-09-29 09:40:16射手座
日期:2014-11-25 08:56:112015年辞旧岁徽章
日期:2015-03-03 16:54:152015年迎新春徽章
日期:2015-03-04 09:49:0315-16赛季CBA联赛之山东
日期:2017-12-21 16:39:1915-16赛季CBA联赛之广东
日期:2016-01-19 13:33:372015亚冠之山东鲁能
日期:2015-10-13 09:39:062015亚冠之西悉尼流浪者
日期:2015-09-21 08:27:57
发表于 2015-09-01 09:09 |显示全部楼层
回复 1# substr函数


[ 1, 8 ], [ 4, 5 ]

为什么不算交叉?

论坛徽章:
7
2015年辞旧岁徽章
日期:2015-03-03 16:54:152015年迎新春徽章
日期:2015-03-04 09:57:092015小元宵徽章
日期:2015-03-06 15:58:18程序设计版块每日发帖之星
日期:2015-08-09 06:20:00每日论坛发贴之星
日期:2015-08-09 06:20:00程序设计版块每日发帖之星
日期:2015-08-22 06:20:00程序设计版块每日发帖之星
日期:2015-08-27 06:20:00
发表于 2015-09-01 09:22 |显示全部楼层
300PB.......这个不是算法层面优化的事情了感觉。。。

论坛徽章:
26
2015亚冠之胡齐斯坦钢铁
日期:2015-06-25 21:40:202015亚冠之柏斯波利斯
日期:2015-08-31 17:03:192015亚冠之柏斯波利斯
日期:2015-11-07 13:10:00程序设计版块每日发帖之星
日期:2015-11-10 06:20:00每日论坛发贴之星
日期:2015-11-10 06:20:00程序设计版块每日发帖之星
日期:2015-11-26 06:20:00程序设计版块每日发帖之星
日期:2015-12-02 06:20:00黄金圣斗士
日期:2015-12-07 17:57:4615-16赛季CBA联赛之天津
日期:2015-12-23 18:34:14程序设计版块每日发帖之星
日期:2016-01-02 06:20:00程序设计版块每日发帖之星
日期:2016-01-06 06:20:00每日论坛发贴之星
日期:2016-01-06 06:20:00
发表于 2015-09-01 12:28 |显示全部楼层
回复 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] 外


   

论坛徽章:
26
2015亚冠之胡齐斯坦钢铁
日期:2015-06-25 21:40:202015亚冠之柏斯波利斯
日期:2015-08-31 17:03:192015亚冠之柏斯波利斯
日期:2015-11-07 13:10:00程序设计版块每日发帖之星
日期:2015-11-10 06:20:00每日论坛发贴之星
日期:2015-11-10 06:20:00程序设计版块每日发帖之星
日期:2015-11-26 06:20:00程序设计版块每日发帖之星
日期:2015-12-02 06:20:00黄金圣斗士
日期:2015-12-07 17:57:4615-16赛季CBA联赛之天津
日期:2015-12-23 18:34:14程序设计版块每日发帖之星
日期:2016-01-02 06:20:00程序设计版块每日发帖之星
日期:2016-01-06 06:20:00每日论坛发贴之星
日期:2016-01-06 06:20:00
发表于 2015-09-01 12:30 |显示全部楼层
回复 2# sunzhiguolu


谢谢 站脚助威

论坛徽章:
26
2015亚冠之胡齐斯坦钢铁
日期:2015-06-25 21:40:202015亚冠之柏斯波利斯
日期:2015-08-31 17:03:192015亚冠之柏斯波利斯
日期:2015-11-07 13:10:00程序设计版块每日发帖之星
日期:2015-11-10 06:20:00每日论坛发贴之星
日期:2015-11-10 06:20:00程序设计版块每日发帖之星
日期:2015-11-26 06:20:00程序设计版块每日发帖之星
日期:2015-12-02 06:20:00黄金圣斗士
日期:2015-12-07 17:57:4615-16赛季CBA联赛之天津
日期:2015-12-23 18:34:14程序设计版块每日发帖之星
日期:2016-01-02 06:20:00程序设计版块每日发帖之星
日期:2016-01-06 06:20:00每日论坛发贴之星
日期:2016-01-06 06:20:00
发表于 2015-09-01 12:32 |显示全部楼层
回复 4# tuyajie
T 神
len(dna) => 100
假设是长度 100 好了

论坛徽章:
23
15-16赛季CBA联赛之吉林
日期:2017-12-21 16:39:27白羊座
日期:2014-10-27 11:14:37申猴
日期:2014-10-23 08:36:23金牛座
日期:2014-09-30 08:26:49午马
日期:2014-09-29 09:40:16射手座
日期:2014-11-25 08:56:112015年辞旧岁徽章
日期:2015-03-03 16:54:152015年迎新春徽章
日期:2015-03-04 09:49:0315-16赛季CBA联赛之山东
日期:2017-12-21 16:39:1915-16赛季CBA联赛之广东
日期:2016-01-19 13:33:372015亚冠之山东鲁能
日期:2015-10-13 09:39:062015亚冠之西悉尼流浪者
日期:2015-09-21 08:27:57
发表于 2015-09-01 13:17 |显示全部楼层
回复 4# tuyajie


是 300bp

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

论坛徽章:
7
2015年辞旧岁徽章
日期:2015-03-03 16:54:152015年迎新春徽章
日期:2015-03-04 09:57:092015小元宵徽章
日期:2015-03-06 15:58:18程序设计版块每日发帖之星
日期:2015-08-09 06:20:00每日论坛发贴之星
日期:2015-08-09 06:20:00程序设计版块每日发帖之星
日期:2015-08-22 06:20:00程序设计版块每日发帖之星
日期:2015-08-27 06:20:00
发表于 2015-09-01 14:40 |显示全部楼层
好吧。好专业的。我去写写看回复 8# ly5066113


   

论坛徽章:
130
技术图书徽章
日期:2013-10-01 15:32:13戌狗
日期:2013-10-25 13:31:35金牛座
日期:2013-11-04 16:22:07子鼠
日期:2013-11-18 18:48:57白羊座
日期:2013-11-29 10:09:11狮子座
日期:2013-12-12 09:57:42白羊座
日期:2013-12-24 16:24:46辰龙
日期:2014-01-08 15:26:12技术图书徽章
日期:2014-01-17 13:24:40巳蛇
日期:2014-02-18 14:32:59未羊
日期:2014-02-20 14:12:13白羊座
日期:2014-02-26 12:06:59
发表于 2015-09-03 19:54 |显示全部楼层
本帖最后由 jason680 于 2015-09-06 13:34 编辑

回复 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
复制代码




您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

SACC2019中国系统架构师大会

【数字转型 架构演进】SACC2019中国系统架构师大会,8.5折限时优惠重磅来袭!
2019年10月31日~11月2日第11届中国系统架构师大会(SACC2019)将在北京隆重召开。四大主线并行的演讲模式,1个主会场、20个技术专场、超千人参与的会议规模,100+来自互联网、金融、制造业、电商等领域的嘉宾阵容,将为广大参会者提供一场最具价值的技术交流盛会。

限时8.5折扣期:2019年9月30日前


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

大会官网>>
  

北京盛拓优讯信息技术有限公司. 版权所有 16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122
中国互联网协会会员  联系我们:huangweiwei@it168.com
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP