[ROSALIND] 패턴을 숫자로

문제 (풀어보기)

DNA 서열이 주어졌을 때 같은 길이의 서열들이 알파벳 순으로 정렬된다면 주어진 서열은 몇 번째 자리에 있는지 출력하시오.

예시

AGT

예상 결과

11

 

해결

def pattern_index(pattern):
    nuc_number = {'A':0, 'C':1, 'G':2, 'T':3}
    if len(pattern) == 1:
        return nuc_number[pattern]
    
    return 4 * pattern_index(pattern[:-1]) + nuc_number[pattern[-1]]

print(pattern_index('CCGAAAACATCCAAGTCTCCAA'))

 

아래 그림에서 처럼 DNA 서열에는 A, C, G, T 로 총 4가지 염기서열만 가능하기 때문에 항상 4개씩 길이가 증가하게 된다. 이 원리를 이용해서 앞 부분(빨간색 표시)의 알파벳 순서만 차례대로 계산하다 보면 주어진 DNA 서열의 최종 위치를 알 수 있다.