파이썬 알고리즘 - 2 탐색 문제

2. 탐색 문제
  탐색 search는 앞으로 볼 수많은 알고리즘에서 사용되는 용어로 이번에는 모든 프로그래머들이 알아야하는 핵심 탐색 알고리즘들을 살펴보겠습니다. 

2.1 DNA 탐색
 컴퓨터 소프트웨어에서 유전자 gene는 문자들의 시퀀스 A, C, G, T로 나타낼수 있는데요. 각각의 문자를 뉴클레오타이드라고 하며, 뉴클레오타이드가 3개가 모인 것을 코돈 codon이라고 부릅니다. 이것에 대한 내용은 아래의 그림 2.1에서 볼수있는데요. 코돈은  단백질 protein을 형성하는 다른 아미노산들과 함께 특정 아미노산을 부호화 하는데, 생물 정보학에서 일반적인 작업은 유전자에 있는 특정한 코돈을 찾는 것이 됩니다.

2.1.1 DNA 저장하기
 4가지 경우에 대한 뉴클레오타이드를 간단한 IntEnum으로 나타내보겠습니다.

from enum import IntEnum
from typing import Tuple, List

Nucleotide = IntEnum('Nucleotide', ('A', 'C', 'G', 'T'))

 여기서 뉴클레오 타이드는 그냥 Enum대신에 IntEnum이라는 타입으로, 이 타입은 비교 연산자도 사용할수 있게 해줍니다. IntEnum에서 이 연산들은 앞으로 구현할 탐색 알고리즘에서 필요한 것들입니다. 튜플과 리스트는 typing 패키지에서 가져와서 사용하면 되겠습니다.

# 타입 별칭 설정
Codon = Tuple[Nucleotide, Nucleotide, Nucleotide]
Gene = List[Codon]

 코돈은 3개의 뉴클레오타이드로 정의할수 있고, 유전자는 코돈들의 목록, 리스트로 정의되겠습니다.


* 주의사항
 나중에 코돈을 다른 코돈이랑 비교할건데,  파이썬에서 빌트인으로 비교할수 있게 되어있어 따로 이 클래스에서 비교 연산자를 구현할 필요는 없습니다.


 일반적으로 인터넷에서 유전자는 유전자들의 시퀀스에 있는 모든 뉴크레오타이드를 문자열로 나타낸것으로 파일 형식같은 것이 됩니다. 이제 가상의 유전자에 대한 문자열을 gene_str이라고 부릅시다.


이제 이 문자열 str을 유전자 gene으로 변환해봅시다.

gene_str = "ACGTGGCTCTCTAACGTACGTACGTACGGGGTTTATATATACCCTAGGACTCCCTTT"

def str_to_gene(s):
    gene = []
    for i in range(0, len(s), 3):
        if (i + 2) >= len(s):
            return gene
        codon = (Nucleotide[s[i]], Nucleotide[s[i+1]], Nucleotide[s[i+2]])
        gene.append(codon)
    return gene

 string_to_gene()은 주어진 str을 이용해서 3개의 문자들을 코돈으로 만들고, 새 유전자의 끝에다가 추가시키는 역활을 수행합니다. 만약 더 이상 뉴클래오타이드 2개가 담겨질 곳이 없으면, 불안전한 유전자로서 끝에 도달한것이 됩니다. 이 경우에 마지막 하나나 2개 남은 뉴클레오 타이드를 무시하면 됩니다.

 string_to_gene()은  gene_str을 gene으로 변환하는데 사용될수 있겠습니다.

my_gene = str_to_gene(gene_str)

2.1.2 선형 탐색
 유전자에 사용할수있는 기본적인 연산 중 하나로 특정 코돈이 어디있는지에 대한 탐색이 될수 있습니다. 여기서 목표는 코돈이 이 유전자 내부에 존재하는것인지 안하는것인지 찾아내기만 하면 되겠는데요.

 선형 탐색은 탐색 공간에 존재하는 모든 요소에 대해서 해당 요소를 찾거나 그 데이터 구조의 끝에 도달할때까지 수행하게 됩니다. 그래서 선형 탐색은 가장 단순하고 명확한 방법이라고 할수 있겠습니다. 하지만 최악의 경우에 선형 탬식시에는 데이터 구조상에 존재하는 모든 요소들을 확인해야 할것이고, 이 구조에 요소의 갯수가 n개가 존재한다면 O(n) 복잡도를 가진다고 할 수 있겠습니다. 

 선형 탐색 함수는 쉽게 정의할수 있는데요. 그냥 데이터 구조상에 있는 모든 요소들을 돌려보고 찾으려고 하는 것과 같은지만 확인하면 되겠습니다. 아래의 코드는 유전자와 코돈이 주어질때, 해당 유전자 안에 입력한 코돈이 존재하는지 검사하게 됩니다.

def linear_contains(gene, key_codon):
    for codon in gene:
        if codon == key_codon:
            return True
        return False

acg = (Nucleotide.A, Nucleotide.C, Nucleotide.G)
gat = (Nucleotide.G, Nucleotide.A, Nucleotide.T)


"""
gene_str = "ACGTGGCTCTCTAACGTACGTACGTACGGGGTTTATATATACCCTAGGACTCCCTTT"

ACG는 gene_str의 0~2에 존재
"""
print("\n-binary search-")
print(linear_contains(my_gene, acg)) # 참
print(linear_contains(my_gene, gat)) #거짓

2.1.3 이진 탐색
 모든 요소를 확인하는것 보다 더 빠른 방법들이 있지만 데이터 구조의 순서에 대해서 알아야 합니다. 만약 정렬된 데이터 구조가 있다면 어느 요소의 인덱스 번호로 해당 요소에 바로 접근할수 있을것이고, 이진 탐색을 할수 있겠습니다. 이런 기준에 따라서 정렬된 리스트는 이진 탐색의 완전한 예시라 할수 있습니다.

 이진 탐색은 정렬된 요소들의 중간 요소와 찾으려는 요소를 비교해서 수행하는데, 비교할 범위를 절반으로 줄이면서 반복 과정을 하게 됩니다. 간단한 예시를 살펴보겠습니다.

 다음과 같은 정렬된 알파벳의 리스트가 있다고 해봅시다.

 [“cat”, “dog”, “kangaroo”, “llama”, “rabbit”, “rat”, “zebra”]

그리고 여기서 “rat”이라는 단어를 찾아보겠습니다.


 1. 우선 7개의 글자에 있는 중간 원소인 “llama”를 찾을수 있습니다.

 2. “rat”은 알파벳 순서를 생각하면 “llama”뒤에 있으므로, “llama”의 뒷쪽에 리스트의 전체 목록 절반 중 어딘가에 있을겁니다. 

3. 이제 목록의 절반에 대해서 1, 2번 단계를 수행하면  “rat”이 어디있는것인지 찾을수 있겠으나 더 이상 탐색할 원소가 존재하지 않게 된다면 이 단어의 리스트에는 “rat”이 없다고 볼수 있겠습니다.

 이진 탐색은 탐색공간을 계속 절반씩 나누므로 최악의 경우에 실행시간이 O(log n)이 됩니다. 그 전에 잠시 생각해봐야할 점은 선형 탐색과는 달리 이진 탐색에서는 이미 정렬된 데이터 구조를 필요하므로, 최적의 정렬 알고리즘으로 정렬을 한 후에 이진 탐색을 수행한다면 O(n log n) 복잡도를 가지게 됩니다.

 만약 기존의 데이터가 정렬되어있지 않은데 탐색을 바로 수행한다고 하면, 선형 탐색처럼 똑같이 동작하게 될겁니다. 하지만 탐색을 여러 차례 수행해야한다고 하는 경우에, 정렬을 해놓은 후 각각에 대한 탐색을 수행하면 시간 비용을 크게 줄일수 있을 겁니다.

  유전자와 코돈을 이용한 이진 탐색 알고리즘에서는 다른 데이터 타입을 사용할 필요가 없는데, 코돈 codon 타입 자체가 유전자 타입의 한 원소와 비교할수 있기 때문입니다.

def binary_contains(gene, key_codon):
    low = 0
    high = len(gene) - 1
    while low <= high:
        mid = (low + high) // 2
        if gene[mid] < key_codon:
            low = mid + 1
        elif gene[mid] > key_codon:
            high = mid - 1
        else:
            return True
     return False

 찾으려는 원소가 중간 원소보다 크거나 작지 않다는 것은 그 원소를 찾은게 되겠습니다. 하지만 루프를 여러번 반복하더라도 False가 반환되었다면 못찾은게 되겠지만요.

 이 함수를 같은 유전자와 코돈으로 돌릴수는 있더라도, 돌리기전에 정렬부터 해야만 하겠습니다.

 

my_sorted_gene = sorted(my_gene)
print("\n-binary search-")
print(binary_contains(my_sorted_gene, acg))
print(binary_contains(my_sorted_gene, gat))

 

 

 

전체

#file_name : dna_search.py
from enum import IntEnum
from typing import Tuple, List

Nucleotide = IntEnum('Nucleotide', ('A', 'C', 'G', 'T'))

# 타입 별칭 설정
Codon = Tuple[Nucleotide, Nucleotide, Nucleotide]
Gene = List[Codon]

gene_str = "ACGTGGCTCTCTAACGTACGTACGTACGGGGTTTATATATACCCTAGGACTCCCTTT"

def str_to_gene(s):
    gene = []
    for i in range(0, len(s), 3):
        if (i + 2) >= len(s):
            return gene
        codon = (Nucleotide[s[i]], Nucleotide[s[i+1]], Nucleotide[s[i+2]])
        gene.append(codon)
    return gene

my_gene = str_to_gene(gene_str)


def linear_contains(gene, key_codon):
    for codon in gene:
        if codon == key_codon:
            return True
        return False

acg = (Nucleotide.A, Nucleotide.C, Nucleotide.G)
gat = (Nucleotide.G, Nucleotide.A, Nucleotide.T)


"""
gene_str = "ACGTGGCTCTCTAACGTACGTACGTACGGGGTTTATATATACCCTAGGACTCCCTTT"

ACG는 gene_str의 0~2에 존재
"""
print("\n-linear search-")
print(linear_contains(my_gene, acg)) # 참
print(linear_contains(my_gene, gat)) #거짓


def binary_contains(gene, key_codon):
    low = 0
    high = len(gene) - 1
    while low <= high:
        mid = (low + high) // 2
        if gene[mid] < key_codon:
            low = mid + 1
        elif gene[mid] > key_codon:
            high = mid - 1
        else:
            return True
    return False


my_sorted_gene = sorted(my_gene)
print("\n-binary search-")
print(binary_contains(my_sorted_gene, acg))
print(binary_contains(my_sorted_gene, gat))

 

실행 결과