如何在Ruby中找到两个字符串中相同子序列的索引？

Question

在这里，类DNA的每个实例对应于一个字符串，如'GCCCAC'。可以从这些字符串构造包含Arrays的子字符串数组。对于这个字符串，有1-mers，2-mers，3-mers，4-mers，5-mers和一个6-mer：

• 6 1-市面汇率：["G", "C", "C", "C", "A", "C"]
• 5 2-市面汇率：["GC", "CC", "CC", "CA", "AC"]
• 4 3-市面汇率：["GCC", "CCC", "CCA", "CAC"]
• 3.4-市面汇率：["GCCC", "CCCA", "CCAC"]
• 2.5-市面汇率：["GCCCA", "CCCAC"]
• 1 6-市面汇率：["GCCCAC"]

这种模式应该是明显的。有关细节，请参阅维基。

问题是编写DNA类的shared_kmers(k，dna2)方法，它返回一个由所有对i，j组成的数组，其中这个DNA对象(接收消息)与dna2共享一个普通的k-mer，在这个dna中的位置I，在dna2的位置j。

dna1 = DNA.new('GCCCAC')
dna2 = DNA.new('CCACGC')

dna1.shared_kmers(2, dna2)
#=> [[0, 4], [1, 0], [2, 0], [3, 1], [4, 2]]

dna2.shared_kmers(2, dna1)
#=> [[0, 1], [0, 2], [1, 3], [2, 4], [4, 0]]

dna1.shared_kmers(3, dna2)
#=> [[2, 0], [3, 1]]

dna1.shared_kmers(4, dna2)
#=> [[2, 0]]

dna1.shared_kmers(5, dna2)
#=> []

Answer 1

class DNA
  attr_accessor :sequencing

  def initialize(sequencing)
    @sequencing = sequencing
  end

  def kmers(k)
    @sequencing.each_char.each_cons(k).map(&:join)
  end

  def shared_kmers(k, dna)
    kmers(k).each_with_object([]).with_index do |(kmer, result), index|
      dna.kmers(k).each_with_index do |other_kmer, other_kmer_index|
        result << [index, other_kmer_index] if kmer.eql?(other_kmer)
      end
    end
  end
end

dna1 = DNA.new('GCCCAC')
dna2 = DNA.new('CCACGC')

dna1.kmers(2)
#=> ["GC", "CC", "CC", "CA", "AC"]

dna2.kmers(2)
#=> ["CC", "CA", "AC", "CG", "GC"]

dna1.shared_kmers(2, dna2)
#=> [[0, 4], [1, 0], [2, 0], [3, 1], [4, 2]]

dna2.shared_kmers(2, dna1)
#=> [[0, 1], [0, 2], [1, 3], [2, 4], [4, 0]]

dna1.shared_kmers(3, dna2)
#=> [[2, 0], [3, 1]]

dna1.shared_kmers(4, dna2)
#=> [[2, 0]]

dna1.shared_kmers(5, dna2)
#=> []

Answer 2

我将只讨论您问题的症结所在，而不涉及类DNA。应该很容易就可以很容易地对接下来的内容进行重组。

码

def match_kmers(s1, s2, k)
  h1 = dna_to_index(s1, k)
  h2 = dna_to_index(s2, k)
  h1.flat_map { |k,_| h1[k].product(h2[k] || []) }
end

​

def dna_to_index(dna, k)
  dna.each_char.
      with_index.
      each_cons(k).
      with_object({}) {|arr,h| (h[arr.map(&:first).join] ||= []) << arr.first.last}
end

示例

dna1 = 'GCCCAC'
dna2 = 'CCACGC'

​

match_kmers(dna1, dna2, 2)
  #=> [[0, 4], [1, 0], [2, 0], [3, 1], [4, 2]] 
match_kmers(dna2, dna1, 2)
  #=> [[0, 1], [0, 2], [1, 3], [2, 4], [4, 0]] 

​

match_kmers(dna1, dna2, 3)
  #=> [[2, 0], [3, 1]] 
match_kmers(dna2, dna1, 3)
  #=> [[0, 2], [1, 3]] 

​

match_kmers(dna1, dna2, 4)
  #=> [[2, 0]] 
match_kmers(dna2, dna1, 4)
  #=> [[0, 2]] 

​

match_kmers(dna1, dna2, 5)
  #=> [] 
match_kmers(dna2, dna1, 5)
  #=> [] 

​

match_kmers(dna1, dna2, 6)
  #=> [] 
match_kmers(dna2, dna1, 6)
  #=> [] 

解释

考虑一下dna1 = 'GCCCAC'。其中包含5种2-mers (k = 2)：

dna1.each_char.each_cons(2).to_a.map(&:join)
  #=> ["GC", "CC", "CC", "CA", "AC"] 

类似地，对于dna2 = 'CCACGC'

dna2.each_char.each_cons(2).to_a.map(&:join)
  #=> ["CC", "CA", "AC", "CG", "GC"]

这些是dna_to_index为dna1和dna2生成的散列的关键。哈希值是相应键从DNA字符串开始的索引数组。让我们为k = 2计算那些散列

h1 = dna_to_index(dna1, 2)
  #=> {"GC"=>[0], "CC"=>[1, 2], "CA"=>[3], "AC"=>[4]} 
h2 = dna_to_index(dna2, 2)
  #=> {"CC"=>[0], "CA"=>[1], "AC"=>[2], "CG"=>[3], "GC"=>[4]} 

h1显示：

• "GC"从dna1的索引0开始
• "CC"从dna1的指数1和2开始
• "CA"从dna1的索引3开始
• "CC"从dna1的索引4开始

h2也有类似的解释。见地图和Array#product。

然后，使用方法match_kmers构造所需的索引对数组( [i, j] )，从而使h1[i] = h2[j]。

现在让我们看看为3-mers (k = 3)生成的散列：

h1 = dna_to_index(dna1, 3)
  #=> {"GCC"=>[0], "CCC"=>[1], "CCA"=>[2], "CAC"=>[3]} 
h2 = dna_to_index(dna2, 3)
  #=> {"CCA"=>[0], "CAC"=>[1], "ACG"=>[2], "CGC"=>[3]} 

我们看到dna1中的前3聚体是"GCC"，从索引0开始.然而，这个3 mer在dna2中没有出现，因此在返回的数组中没有[0, X]元素(X只是一个占位符)。在第二个散列中，"CCC"也不是一个键。然而，第二个散列中存在"CCA"和"CAC"，因此返回的数组是：

h1["CCA"].product(h2["CCA"]) + h1["CAC"].product(h2["CAC"]) 
  #=> [[2, 0]] + [[3, 1]]
  #=> [[2, 0], [3, 1]]

Answer 3

首先，我将编写一种方法来枚举给定长度的子序列(即k)：

class DNA
  def initialize(sequence)
    @sequence = sequence
  end

  def each_kmer(length)
    return enum_for(:each_kmer, length) unless block_given?

    0.upto(@sequence.length - length) { |i| yield @sequence[i, length] }
  end
end

DNA.new('GCCCAC').each_kmer(2).to_a
#=> ["GC", "CC", "CC", "CA", "AC"]

在此基础上，您可以使用嵌套循环轻松地收集相同k的索引：

class DNA
  # ...

  def shared_kmers(length, other)
    indices = []
    each_kmer(length).with_index do |k, i|
      other.each_kmer(length).with_index do |l, j|
        indices << [i, j] if k == l
      end
    end
    indices
  end
end

dna1 = DNA.new('GCCCAC')
dna2 = DNA.new('CCACGC')

dna1.shared_kmers(2, dna2)
#=> [[0, 4], [1, 0], [2, 0], [3, 1], [4, 2]]

不幸的是，上面的代码为接收器中的每个k-mer遍历other.each_kmer。我们可以通过预先构建一个包含other中每个k-mer的所有索引的散列来优化这一点：

class DNA
  # ...

  def shared_kmers(length, other)
    hash = Hash.new { |h, k| h[k] = [] }
    other.each_kmer(length).with_index { |k, i| hash[k] << i }

    indices = []
    each_kmer(length).with_index do |k, i|
      hash[k].each { |j| indices << [i, j] }
    end
    indices
  end
end