入力文字列と同じサイズのオカレンスのベクトルを作成する

Question

私はPythonには新しく、助けが必要でした。

私は今の要素が特定の文字のカウントしている3つのベクトルを作成したい文字列などACAACGG

を持っています。

例えば、「A」のために、これは「C」の場合（1123333） を生成する、これが生成します（0111222） など私は、カウントの結果を入れてするかどうかはわかりません

文字列またはベクトルに変換します。 これは文字列内の文字の出現回数をカウントするのと似ていると思いますが、文字列をどのように実行してカウント値を各点に配置するかわかりません。

参考のため、私はBurrows-Wheeler変換を実装して文字列検索に使用しています。しかし、私はどのように文字の出現ベクトルを作成するか分からない。

def bwt(s): 
    s = s + '$' 
    return ''.join([x[-1] for x in 
    sorted([s[i:] + s[:i] for i in range(len(s))])]) 

これは私に変換を与え、私はそのための発生ベクトルを作成しようとしています。最終的に、これを使ってDNA文字列のリピートを検索したいと思います。

ご協力いただければ幸いです。

Answer 1

ベクトルを入れたいタイプはわかりませんが、listをintに戻す関数があります。

In [1]: def countervector(s, char): 
    ....:  c = 0 
    ....:  v = [] 
    ....:  for x in s: 
    ....:   if x == char: 
    ....:    c += 1 
    ....:   v.append(c) 
    ....:  return v 
    ....: 

In [2]: countervector('ACAACGG', 'A') 
Out[2]: [1, 1, 2, 3, 3, 3, 3] 

In [3]: countervector('ACAACGG', 'C') 
Out[3]: [0, 1, 1, 1, 2, 2, 2] 

また、ここでそれを行うにははるかに短い方法ですが、それはおそらく長い文字列に非効率的になります。

def countervector(s, char): 
    return [s[:i+1].count(char) for i, _ in enumerate(s)] 

私はそれが役に立てば幸い。

Answer 2

ここで約束したのは、私が書いた完成したスクリプトです。参考までに、Burrows-Wheeler変換を使用してDNAの文字列に繰り返し一致させようとしています。基本的には、長さMのDNA鎖を取り、その文字列内のすべての繰り返しを見つけることです。したがって、例として、私が奇妙なacaacgを持っていて、サイズ2のすべての重複した部分文字列を検索した場合、カウントは1になり、開始位置は0,3になります。文字列[0：2]と文字列[3：5]を入力して、実際に一致し、結果が "ac"であることを確認できます。

バローズウィーラーについて学ぶことに興味がある人は、ウィキペディアで検索すると非常に有益な結果が得られます。ここにスタンフォード出身の別の情報源もあります。 http://www.stanford.edu/class/cs262/notes/lecture5.pdf

ここでは、私がこれで取り組まなかったいくつかの問題があります。まず、BW変換を作成するためにn^2空間を使用しています。また、私はサフィックス配列を作成し、それをソートし、それを数字に置き換えているので、少しのスペースが必要になります。しかし、最後には私は実際には事実行列、最後の列、単語自体を格納するだけです。

4^7より大きい文字列のRAMの問題にもかかわらず（これは文字列のサイズが40,000であってもそれ以上ではありません...）、私はこれを月曜日の前と同じように見ていますPythonでやる方法は、私の名前とこんにちはの世界を印刷することでした。

# generate random string of DNA 
def get_string(length): 
    string="" 
    for i in range(length): 
     string += random.choice("ATGC") 
    return string 

# Make the BW transform from the generated string 
def make_bwt(word): 
    word = word + '$' 
    return ''.join([x[-1] for x in 
     sorted([word[i:] + word[:i] for i in range(len(word))])]) 
# Make the occurrence matrix from the transform   
def make_occ(bwt): 
    letters=set(bwt) 
    occ={} 
    for letter in letters: 
     c=0 
     occ[letter]=[] 
     for i in range(len(bwt)): 
      if bwt[i]==letter: 
      c+=1 
      occ[letter].append(c) 
    return occ 

# Get the initial starting locations for the Pos(x) values 
def get_starts(word): 
    list={} 
    word=word+"$" 
    for letter in set(word): 
     list[letter]=len([i for i in word if i < letter]) 
    return list 

# Single range finder for the BWT. This produces a first and last position for one read. 
def get_range(read,occ,pos): 
    read=read[::-1] 
    firstletter=read[0] 
    newread=read[1:len(read)] 
    readL=len(read) 
    F0=pos[firstletter] 
    L0=pos[firstletter]+occ[firstletter][-1]-1 

    F1=F0 
    L1=L0 
    for letter in newread: 
     F1=pos[letter]+occ[letter][F1-1] 
     L1=pos[letter]+occ[letter][L1] -1 
    return F1,L1 

# Iterate the single read finder over the entire string to search for duplicates 
def get_range_large(readlength,occ,pos,bwt): 
    output=[] 
    for i in range(0,len(bwt)-readlength): 
     output.append(get_range(word[i:(i+readlength)],occ,pos)) 
    return output 

# Create suffix array to use later 
def get_suf_array(word): 
    suffix_names=[word[i:] for i in range(len(word))] 
    suffix_position=range(0,len(word))     
    output=zip(suffix_names,suffix_position) 
    output.sort() 
    output2=[] 
    for i in range(len(output)):       
     output2.append(output[i][1]) 
    return output2 

# Remove single hits that were a result of using the substrings to scan the large string 
def keep_dupes(bwtrange): 
    mylist=[] 
    for i in range(0,len(bwtrange)): 
     if bwtrange[i][1]!=bwtrange[i][0]: 
      mylist.append(tuple(bwtrange[i])) 
    newset=set(mylist) 
    newlist=list(newset) 
    newlist.sort() 
    return newlist 

# Count the duplicate entries 
def count_dupes(hits): 
    c=0 
    for i in range(0,len(hits)): 
     sum=hits[i][1]-hits[i][0] 
     if sum > 0: 
      c=c+sum 
     else: 
      c 
    return c 

# Get the coordinates from BWT and use the suffix array to map them back to their original indices 
def get_coord(hits): 
    mylist=[] 
    for element in hits: 
     mylist.append(sa[element[0]-1:element[1]]) 
    return mylist 

# Use the coordinates to get the actual strings that are duplicated 
def get_dupstrings(coord,readlength): 
    output=[] 
    for element in coord: 
     temp=[] 
     for i in range(0,len(element)):   
      string=word[element[i]:(element[i]+readlength)] 
      temp.append(string) 
     output.append(temp) 
    return output 

# Merge the strings and the coordinates together for one big list. 
def together(dupstrings,coord): 
    output=[] 
    for i in range(0,len(coord)): 
     merge=dupstrings[i]+coord[i] 
     output.append(merge) 
    return output 

Now run the commands as follows 
import random # This is needed to generate a random string 
readlength=12 # pick read length 
word=get_string(4**7) # make random word 
bwt=make_bwt(word) # make bwt transform from word 
occ=make_occ(bwt) # make occurrence matrix 
pos=get_starts(word) # gets start positions of sorted first row  
bwtrange=get_range_large(readlength,occ,pos,bwt) # Runs the get_range function over all substrings in a string.  
sa=get_suf_array(word) # This function builds a suffix array and numbers it. 
hits=keep_dupes(bwtrange) # Pulls out the number of entries in the bwt results that have more than one hit. 
dupes=count_dupes(hits) # counts hits 
coord=get_coord(hits) # This part attempts to pull out the coordinates of the hits. 
dupstrings=get_dupstrings(coord,readlength) # pulls out all the duplicated strings 
strings_coord=together(dupstrings,coord) # puts coordinates and strings in one file for ease of viewing. 
print dupes 
print strings_coord