Finding a Spliced Motif

문제해설

Motif란 뉴클리오타이드나 아미노산의 생물학적으로 중요한 패턴을 말합니다. Motif는 두 종의 생물에서 동일하게 나타날 수 있는데, 이는 그 Motif가 존재하는 종들에게 동일한 기능이 존재한다고 볼 수 있는 근거가 됩니다.

RNA splicing은 Motif를 찾는 것을 더 복잡하게 만듭니다. 왜냐하면 Finding a Motif in DNA문제에서와 달리, Motif는 연속적이지 않기 때문입니다. 단백질로 코딩되는 유전자는 아미노산으로 번역되는 exon과 그렇지 않은 intron으로 나뉘게 되는데, exon에 motif가 불연속적으로 존재 할 수 있습니다. 예를 들면 AUGATGCGATUAG라는 exon1이 있고, AUGTGCGTAAGCUAG라는 exon2가 있다고 했을 때, CCG Motif exon1과 exon2에 흩어져서 존재할 수도 있습니다. 이 문제는 Motif를 찾는 것을 단순화 시켜 연속적인 Motif를 찾는 것에서 벗어나 실제는 불연속적인 Motif의 위치를 찾는 문제입니다.

---

문제 정의

부분서열(subsequence)은 전체서열에 순서대로 담겨있는 심볼들의 잡합입니다.(e.g. ACG는 TATGCTAAGATC 의 부분서열입니다. 부분서열의 인덱스들은 부분서열의 요소가 전체서열에 존재하는 위치입니다. 따라서 TATGCTAAGATC에서 ACG의 인덱스는 (2, 5, 9)로 나타낼 수 있습니다.

부분서열은 여러 위치를 가질 수 있으므로 부분서열은 다수의 인덱스 집합을 가질 수 있습니다. 동일한 인덱스는 하나 이상의 부분서열의 형태로 재사용 될 수 있습니다.
하위 문자열은 여러 위치 를 가질 수 있으므로 하위 시퀀스는 여러 인덱스 컬렉션을 가질 수 있으며 동일한 인덱스는 하위 시퀀스의 둘 이상의 모양에서 재사용될 수 있습니다. 예를 들어, ACG는 8가지 다른 방식으로 AACCGGTT의 부분서열입니다. (AACCGGTT, AACCGGTT ....)

Given : 두개의 DNA 서열 s, t가 (1kbp 를 넘지 않는 길이로) FASTA format으로 주어집니다.(Two DNA strings s and t (each of length at most 1 kbp) in FASTA format.)

Return : 서열 s에서 부분서열인 t가 존재하는 인덱스 집합 중 하나를 반환하세요. 여러개의 집합이 존재 할 수 있지만 하나만 반환해도 상관 없습니다.(One collection of indices of s in which the symbols of t appear as a subsequence of s. If multiple solutions exist, you may return any one.)

Sample Dataset

Rosalind_14
ACGTACGTGACG
Rosalind_18
GTA

Sample Output

3 8 10

해결 방법

문제의 핵심은 s, ACGTACGTGACG와 t, GGTA가 주어졌을 때, 먼저 G의 index를 찾았을때, 다음 G의의 index를 찾는 것입니다. 해결법은 t의 서열을 하나식 iterate 할 때마다, 찾은 해당 index까지의 서열을 제외하고 그 다음 서열을 찾는 것입니다.

def find_motif_loc(d):  # d에는 s 와 t 서열이 들어 있습니다.
    idxes = [0] # sum 을 할때 빈 리스트를 합하면 error가 남으로 idxes에 0을 넣어줍니다.
    s = d["s"]
    # t 서열을 iterate 합니다.
    for t in d["t"]:
    	# 이전까지의 인덱스를 합친 값의 인덱스로부터 다음 t 서열의 요소의 위치를 찾아냅니다.
        next_idx = d["s"][sum(idxes):].index(t) + 1 
        idxes.append(next_idx) # idxes에 추가합니다.
    
    # 맨 처음 값을 제외하고 idxes를 누적한 리스트를 반환합니다.
    return tail(len(d["t"]),accumulate(add, idxes))

전체 코드 는 깃허브에 저장해 두었습니다.