🧬 2.1 고정된 패턴을 찾는 단순 알고리즘

---

2.1. 패턴찾기의 중요성

🧬 생물학적 정보는 DNA 서열로 유지되기 때문에 서열 데이터의 패턴 분석은 중요함
🧬 서열 데이터의 패턴은 분자의 특정 기능에 연관되어 있음
🧬 단백질이 특정 기능을 수행하려면 단백질의 구조에 특정한 패턴이 필요하며, 그것에 상응하는 DNA 서열 패턴이 존재
🧬 또한 DNA 서열에는 유전자 발현량을 조절하는 결합부위 등이 관련되어 있기도 함

2.1.1. 고정된 패턴을 찾는 단순 알고리즘

---

🧬 찾으려는 패턴의 처음 위치를 찾거나 찾으려는 패턴의 모든 위치를 찾는 알고리즘
🧬 search_first_occ( ) 함수 생성 : 패턴이 처음 나타나는 위치를 반환하거나 발생하지 않으면 -1을 반환함
🧬 search_all_occurences( ) 함수 생성 : 서열에서 패턴이 일치하는지 검사하고 위치 리스트를 반환함. 없으면 빈 리스트 반환
🧬 test_pat_search( ) 함수 생성 : 사용자가 입력한 서열 데이터에도 적용가능

---

💊 search_first_occ( )

• i : DNA seq 의 인덱스
• j : pattern seq 의 인덱스
• DNA 서열과 pattern 서열의 첫 염기가 다르면 i += 1 에 의해 DNA 서열을 한칸씩 이동하면서 읽음
• 그러다가 첫 염기가 같으면 j = j + 1 에 의해 DNA([ i+j ]) 서열과 pattern([ j ]) 서열을 한칸씩 이동하면서 읽음
• 만약 이러한 과정 중에 다른 염기가 발견되면 i += 1 을 실행하고 j는 다시 0으로 초기화
• 찾는 pattern 과 완전히 일치하면 j == len(pattern) 에 의해 found = True
• pattern 이 DNA seq 에서 처음 나타나는 위치인 i 를 반환함

def search_first_occ(seq, pattern):
    found = False
    i = 0
    while i < len(seq)-len(pattern) and not found:
        j = 0
        while j < len(pattern) and pattern[j]==seq[i+j]:
            j = j + 1
        if j == len(pattern):
            found = True
        else:
            i += 1
    if found: return i
    else: return -1
        
seqDNA = "ATAGAATAGATAATAGTC"
print(search_first_occ(seqDNA, "GAAT"))
print(search_first_occ(seqDNA, "TATA"))

>> 3
  -1

---

💊 search_all_occurrences( )

• i : DNA seq 의 인덱스
• j : pattern seq 의 인덱스
• DNA seq 과 pattern seq 의 첫 염기가 다르면 for문에 의해서 i += 1 이 되면서 DNA 서열을 한칸씩 이동하면서 읽음
• 첫 염기가 같으면 j = j + 1 에 의해 DNA ([ i+j ]) 서열과 pattern seq ([ j ]) 서열을 한칸씩 이동하면서 읽음
• 그러다가 완전히 일치하는 패턴이 발견되면 DNA seq에서 처음 나타나는 위치인 i 를 res 리스트에 추가
• for 문에 의해서 모든 DNA 염기서열에 대해서 search 가 가능함
• 이렇게 위치를 추가한 리스트인 res 반환

def search_all_occurrences(seq, pattern):
    res = []
    for i in range(len(seq)-len(pattern)+1):
        j = 0
        while j < len(pattern) and pattern[j]==seq[i+j]:
            j = j + 1
        if j == len(pattern):
            res.append(i)
    return res

seqDNA = "ATAGAATAGATAATAGTC"
print(search_all_occurrences(seqDNA, "AAT"))

>> [4, 11]

---

def test_pat_search():
    seq = input("Input sequence: ")
    pat = input("Input pattern: ")
    print(pat, "occrs in the following positions: ")
    print(search_all_occurrences(seq, pat))
    
test_pat_search()

>>
Input sequence: ATGGGATCGTAGTCGTACTAGCTAGCTGATGGTACTCGATAGTCTACGTAGCTAGTGGTACTGGATGGTACTCAGTAACAT
Input pattern: AT
AT occrs in the following positions: 
[0, 5, 28, 38, 64, 79]

---

🧬 이번 포스팅에서는 단순하게 서열들을 한칸씩 이동하면서 비교하는 알고리즘을 다뤄보았다. 하지만 이렇게 일일이 비교하는 알고리즘은 너무 많은 실행을 해야하는 경우가 있고, 데이터 양이 많은 생명데이터에는 적합하지 않다고 생각한다.

🧬 다음 포스팅에서는 좀 더 향상된 보이어-무어 알고리즘에 대해서 배워보자.

---

💡 Bioinformatics Algorithms(에이콘출판, 2020)를 공부하고 개인 학습용으로 정리한 자료입니다.