Encoding Suffix Trees

Problem

Figure 1. The suffix tree for s = GTCCGAAGCTCCGG. Note that the dollar sign has been appended to a substring of the tree to mark the end of s. Every path from the root to a leaf corresponds to a unique suffix of GTCCGAAGCTCCGG, and each leaf is labeled with the location in s of the suffix ending at that leaf.

Given a string ss having length nn, recall that its suffix tree T(s)T(s) is defined by the following properties:

• T(s)T(s) is a rooted tree having exactly nn leaves.
• Every edge of T(s)T(s) is labeled with a substring of s∗s∗, where s∗s∗ is the string formed by adding a placeholder symbol $ to the end of ss.
• Every internal node of T(s)T(s) other than the root has at least two children; i.e., it has degree at least 3.
• The substring labels for the edges leading down from a node to its children must begin with different symbols.
• By concatenating the substrings along edges, each path from the root to a leaf corresponds to a unique suffix of s∗s∗.

Figure 1 contains an example of a suffix tree.

Given: A DNA string ss of length at most 1kbp.

Return: The substrings of s∗s∗ encoding the edges of the suffix tree for ss. You may list these substrings in any order.

Sample Dataset

ATAAATG$

Sample Output

AAATG$
G$
T
ATG$
TG$
A
A
AAATG$
G$
T
G$
$

 

 이 문제는 suffix tree의 모든 edge를 출력하는 문제이다. suffix tree는 모든 접미사들을 간단하게 표현하기 위해 만든 tree인데, 잘 살펴보면 일종의 trie 인것을 알 수 있다. Introdution to Patter Matching에서 살펴본 trie는 여러 개의 문자열을 나타닐때 최대한 겹치는 부분은 같이 표현하고 달라지는 부분은 갈라져서 그래프로 모든 문자열을 표현할 수 있게 해준다. suffix tree는 모든 접미사들을 달라지는 부분만 갈라져서 표현한단 점에서 같지만 trie는 edge 하나에 하나의 문자를, suffix tree는 edge 하나에 하나에서 여러개의 문자를 표현한단 점에서 다르다.

 필자는 이 점을 고려하여, 첫번째로 모든 suffix를 구하고, 그 다음 그 suffix들로 trie를 만들고, 이 trie에서 edge들을 합쳐서 suffix tree의 edge를 구하는 방식을 취했다.

def making_suffs(seq):#모든 suffix구하기
    suffs=[]
    for i in range(len(seq)):
        suffs.append(seq[i:])

    return suffs
def building_trie(patterns):#trei만들기
    trie={1:{}}#trie를 저장
    node_id=1#새로운 노드 나타날시 노드id매겨주기

    for pattern in patterns:#여러 문자열들 중 하나의 문자열
        current_node = 1#일단 처음부터 시작
        for char in pattern:#하나의 문자열에서 하나의 알파벳
            if char in trie[current_node]:#지금 있는 노드에서 이 알파벳으로 이어진 노드가 있다면
                current_node = trie[current_node][char]#지금 노드는 이어진 노드로 이동
            else:#만약 없다면
                node_id+=1#새로운 노드id 매기기
                trie[current_node][char] = node_id#지금 노드와 새로운 노드 이어주기
                current_node = node_id#지금 노드는 새로운 노드로

                trie[node_id]={}#새로운 노드에서 이어지는 딕셔너리 만들기

    return trie

def finding_edges(now_node,edge,graph):#edge만들기
    if len(graph[now_node]) == 0:#leaf면
        total_edge.append(edge)
        return
    if len(graph[now_node])>=2 and edge!='':#branching 이면
        total_edge.append(edge)
        edge=''
    for k,v in graph[now_node].items():
        finding_edges(v,edge+k,graph)

if __name__ == '__main__':
    with open(r"파일경로",'r') as f:
        seq = f.readline().rstrip()

total_edge=[]
suffs= making_suffs(seq)
trie=building_trie(suffs)

finding_edges(1,'',trie)
with open(r"파일경로",'w') as wf:
    for i in total_edge:
        print(i,file=wf)

 

ntroduction to Pattern Matching

Introduction to Pattern Matching ㅇ