5

シンボルのリストを指定して、可能なすべての長さの文字列 ( k-merと呼ばれる) を繰り返し処理したいと思います。たとえば、 とk = 3の場合symbols = {A, C, G, T}:

AAA
AAC
AAG
...
TTG
TTT

文字列を生成するコードは次のとおりです。

local k = 3
local bases = {'A', 'C', 'T', 'G'}

-- Generate the string (AAA...AAA)
local kmer_gen = {}
for i = 1,k do kmer_gen[i] = "A" end
local kmer = table.concat(kmer_gen)

それは機能しますが、確かに見栄えがよくありません。これをよりエレガントに実現できますか?

さて、可能なk-merを反復する方法がわかりません。1 つの解決策は、各文字を置き換え続けることですが、これは効率的ではありません。もう 1 つの方法は、バイナリ (各 2 ビットが基数を表す) からデコードすることですが、実装がわかりにくく、ビット単位の演算が必要です。他の考えはありますか？

4

2 に答える 2

6

これは、イテレータを使用したソリューションです。これは、Lua で知っておく価値のある手法であるコルーチンの良い例です。http://www.lua.org/pil/9.3.htmlも参照してください。

local bases = {'A', 'C', 'T', 'G'}

local function allstrings(n,t,k,s)
    k=k or 1
    s=s or {}
    if k>n then
        coroutine.yield(table.concat(s))
    else
        for i=1,#t do
            s[k]=t[i]
            allstrings(n,t,k+1,s)
        end
    end
end

local function kmer(n,t)
    return coroutine.wrap(allstrings),n,t
end

for w in kmer(3,bases) do
    print(w)
end
于 2013-11-06T10:44:54.297 に答える
4

これは、おそらく使用する比較的単純な末尾再帰ソリューションです。

local bases = {'A', 'C', 'T', 'G'}

local function kmers(n, prev)
  prev = prev or {''}
  if n <= 0 then return prev end
  local k,r = 1,{}
  for i=1,#prev do
    for j=1,#bases do
      r[k] = prev[i] .. bases[j]
      k = k+1
    end
  end
  return kmers(n-1, r)
end

_3mers = kmers(3) -- usage example

注:手動r[#r+1]で管理する代わりに書き込むこともできますが、このような場合 (演算子は です)kはそれほど複雑ではなく、大幅に高速化されます。#O(log n)

于 2013-11-06T09:25:15.817 に答える