从几个给定的集合中生成所有可能的 DNA 序列

发布于 2024-08-12 21:46:02 字数 710 浏览 3 评论 0原文

我已经尝试解决这个问题有一段时间了，但一直无法想出一个好的解决方案。这里是：

给定多个集合：

set1: A, T
set2: C
set3: A, C, G
set4: T
set5: G

我想从集合列表中生成所有可能的序列。在此示例中，序列的长度为 5，但可以是最多 20 左右的任意长度。对于位置 1，可能的候选值分别为“A”和“T”，对于位置 2，唯一的选项是“C”，因此在。

上面示例的答案是：

ACATG、ACCTG、ACGTG、TCATG、TCCTG、TCGTG

我正在 ruby 中执行此操作，并且我将不同的集合作为主数组中的数组：

[[A, T], [C], [A, C, G], [T], [G]]

起初我认为递归解决方案是最好的，但是我不知道如何正确设置它。

我的第二个想法是创建另一个相同大小的数组，每个数组都有一个索引。因此 00000 将对应于“ACATG”上方的第一个序列，而 10200 将对应于“TCGTG”。从 00000 开始，我会将最后一个索引加一，并用所讨论的集合的长度对其取模（上面的 set1 为 2，上面的 set2 为 1），如果计数器回绕，我会将其归零并将前一个索引加一。

但我越想这个解决方案，它对于这个非常小的问题来说就显得太复杂了。一定有一个我缺少的更直接的解决方案。有人可以帮我吗？

/缺口

原文

I have been trying to wrap my head around this for a while now but have not been able to come up with a good solution. Here goes:

Given a number of sets:

set1: A, T
set2: C
set3: A, C, G
set4: T
set5: G

I want to generate all possible sequences from a list of sets. In this example the length of the sequence is 5, but it can be any length up to around 20. For position 1 the possible candidates are 'A' and 'T' respectively, for position 2 the only option is 'C' and so on.

The answer for the example above would be:

ACATG, ACCTG, ACGTG, TCATG, TCCTG, TCGTG

I am doing this in ruby and I have the different sets as arrays within a master array:

[[A, T], [C], [A, C, G], [T], [G]]

At first I thought a recursive solution would be best but I was unable figure out how to set it up properly.

My second idea was to create another array of the same size with an index for each set. So 00000 would correspond to the first sequence above 'ACATG' and 10200 would correspond to 'TCGTG'. Beginning with 00000 I would increase the last index by one and modulo it with the length of the set in question (2 for set1, 1 for set2 above) and if the counter wrapped around I would zero it and increase the previous one by one.

But the more I thought about this solution it seemed too complex for this very small problem. There must be a more straight-forward solution that I am missing. Could anyone help me out?

/Nick

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

咿呀咿呀哟 2024-08-19 21:46:02

Ruby 1.8.7 中的 Array 类有一个 Array#product 方法，该方法返回相关数组的笛卡尔积。

irb(main):001:0> ['A', 'T'].product(['C'], ['A', 'C', 'G'], ['T'], ['G'])
=> [["A", "C", "A", "T", "G"], ["A", "C", "C", "T", "G"], ["A", "C", "G", "T", "G"],     ["T", "C", "A", "T", "G"], ["T", "C", "C", "T", "G"], ["T", "C", "G", "T", "G"]]

The Array class in Ruby 1.8.7 has an Array#product method, which returns the cartesian product of the arrays in question.

irb(main):001:0> ['A', 'T'].product(['C'], ['A', 'C', 'G'], ['T'], ['G'])
=> [["A", "C", "A", "T", "G"], ["A", "C", "C", "T", "G"], ["A", "C", "G", "T", "G"],     ["T", "C", "A", "T", "G"], ["T", "C", "C", "T", "G"], ["T", "C", "G", "T", "G"]]

回复收藏 0 原文

~没有更多了~