dimer (길이가 2인 k-mer) 조합은 AA 부터 CC 까지 16가지가 존재한다.그러면 확률적으로 각각의 dimer 가 등장할 확률은 1/16으로 동일하므로, 실제 서열에서도 이와 비슷한 분포를 갖고 있어야 할 것 같다.그런데 사람 게놈을 살펴봤더니 그렇지 않았다.특히 CG 패턴은 매우 적었다.이런 현상을 가리켜 CG-Island 라고 부른다. 이 문제는 The Fair Bet Casino 문제로 비유할 수 있다.어떤 카지노 게임이 동전 던지기의 결과인 H/T 로 결과가 정해진다고 해보자. 그런데 이때 동전은 '공정한 동전 = 모두 1/2 확률' 과 '편향된 동전 = 앞면이 3/4' 이 있다. 따라서 이렇게 조건부 확률로 표현할 수 있다. 그리고 공정한 동전과 편향된 동전의 교체가 적발되면 좋지 않..
팬케이크 뒤집기 문제어떤 무작위 수열이 존재한다.내가 할 수 있는 연산은 수열의 prefix를 뒤집는 연산만 가능할 때,주어진 수열을 정렬하는데 필요한 최소한의 뒤집기 연산 횟수를 구하는 문제 그리디 접근법으로 떠올릴 수 있는 제일 간단한 해결 방법 :현재 남아있는 제일 큰 수를 맨 위로 오도록 뒤집는다 → 전체를 뒤집는다 → 제일 큰 수가 맨 밑으로 간다. 이를 반복하면 된다. 이 알고리즘은 분명 잘 작동한다.하지만 더 적은 횟수로 문제를 풀 수는 없을까? 4번에 정렬할 수 있다! 사람과 쥐의 게놈은 비슷함 (여러 번의 재배치가 존재하는 차이점이 있다.)이때 발생 가능한 재배치의 종류는 크게 4가지 1. Reversal (이번 글에서 주로 정리할 내용)2. Fusion : 2개의 contig 가..
DNA로 돌아와서, 자주 반복되는 DNA motif 를 찾거나, 가장 자주 등장하는 k-mer를 찾거나, 특정한 k-mer가 얼마나 자주 등장하는지 알고 싶을 때 문자열 패턴 매칭 알고리즘을 사용할 수 있다. 제일 근본적인 패턴 매칭 문제는 문자열에 특정 패턴이 존재하는지 확인하고, 존재한다면 그 위치는 어디인지 찾는 것 제일 나이브한 방법은 문자열을 직접 순회하면서 찾는 것이다.이때는 패턴의 길이가 n이고, 문자열의 길이가 m일 때, O(mn) 의 시간이 걸린다. 근데 이걸 조금 더 최적화 해보면,위와 같은 문자열에서 ssi 를 찾는다고 할 때, SS까지 일치했는데, i가 m이랑 불일치해서 실패한 경우,우리는 그 다음에 시도할 위치를 한번 건너뛸 수 있다.우리가 찾는 패턴의 prefix ss가 지금 ..
(문해기는 시간이 없어서 간결하게 정리할 예정..) 지금까지는 DNA에 대한 이야기였다면 이번에는 단백질에 대한 이야기를 해보자.단백질은 아미노산들의 조합으로 구성된다.각각의 아미노산은 탈수결합을 통해 합쳐지며, 그 결과물을 residue 라고 부른다.이때 20가지 아미노산 residue 의 분자량은 이미 정확하게 잘 알려져 있다. PIT 라는 고분자에 대해, PIT, PTI, ITP 등 순서는 분자량에 영향을 주지 않는다.따라서 이들 각각을 2개로 쪼갰을 때, (PI, IT) 와 (PT, TI) 의 분자량 합은 같다 (?) 20가지 아미노산에 대해 결합에 참여했을 때 물이 빠진 상태의 분자량을 하나의 테이블에 저장할 수 있고,이를 Daltons 이라고 부른다. 더보기 AminoAcid = { '..
지금까지는 어떻게하면 여러개의 DNA 시퀀스에서 공통된 motif 를 찾고, 찾아낸 motif 를 기존 DNA 에서 어떻게 표현할 것인지 (정렬할 것인지) 다양한 방법에 대해 정리하였다. 이번 글부터는 각각의 DNA 조각들을 모아서 하나의 게놈을 만드는 방법을 정리해본다. 아이디어 100권의 책을 파쇄한 뒤, 각 조각들을 잘 조립해서 하나의 페이지를 복원하려고 한다. 각 조각들을 올바르게 조립해서 하나의 페이지로 복원할 때, 각 조각에서 겹치는 부분들을 이용해서 페이지를 복원할 수 있다. DNA 조각들을 모아서 하나의 게놈을 만들 때도 비슷한 방법을 사용하여 복원할 수 있다.이때 이 방법을 위해서 그래프를 정의할 필요가 있다. 그래프는 read fragment 를 정점으로 하고, 두 fragment 사..
Affine Gap 같은 정렬이어도, 왼쪽 것이 더 좋다.어떻게하면 왼쪽처럼 정렬하도록 만들 수 있을까? 여러개 정렬하기한번에 정렬하기 vs 2개씩 정렬하기 메모리 공간 최적화슬라이딩 윈도우분할 정복 ( 심화 내용이라는 느낌이 들어서 정리를 후순위로 미룸 )
지난 글까지는 여러개의 DNA 시퀀스에서 공통 motif (유사한 motif) 를 찾는 방법에 대해 정리하였다.이번 글부터는 지난 글에서 찾아낸 각 DNA 염기 서열 속 motif 들 또는 전체 DNA 염기 서열이 얼마나 유사한지를 확인하기 위해, 정렬하는 방법에 대해 정리한다. 예를 들어, 위 문자열은 사람, 개, 고양이, 돼지의 인슐린 단백질의 아미노산 서열을 나타낸 모습이다.이 서열은 얼마나 유사할까? 유사도를 측정하는 방법 중 하나는 각 문자열을 같은 문자끼리 '정렬' 하는 것이다.위 모습은 4개의 인슐린 단백질 아미노산 염기 서열을 직접 손으로 정렬한 모습을 보여준다.그리고 꽤나 긴 공통 서열이 나타나는 것을 알 수 있다. 그런데 이 공통 서열이 과연 우리가 찾을 수 있는 최적의 서열일까?..
Pruning Trees지난 글에서 정리했던 브루트포스 & Score 함수를 이용한 motif 탐색 알고리즘은 시간이 매우 오래 걸렸다.이는 각 Score 함수의 실행 시간은 짧았지만 motif 조합을 다 해봐야했기 때문에 Score 함수의 호출 횟수가 너무 많았기 때문이다.하지만 모든 경우에 대해 매번 Score 함수를 호출해야만할까? pruning tree 알고리즘을 사용하여 호출 횟수를 줄여보자.이 알고리즘은 현재까지 발견한 최적해와 비교하여, 현재 하려는 계산이 더 최적이 될 것 같지 않을 때 굳이 계산해보지 않고 과감하게 건너뛰는 방법이다. 예를 들어보자.10개의 DNA에서 공통적으로 등장하는 10-mer motif 를 찾으려고 한다.이때 4개 DNA 에 대해서 점수를 계산했더니 17점이 나왔고..
지난 글에서는 초기 코로나 바이러스의 DNA 패턴을 분석하는 방법으로 k-mers 라는 부분 문자열로 나누어서 분석하는 방법을 알아보았다. 지난 글 마지막에서 보았을 때는, 초기 코로나 바이러스의 스파이크 단백질 염기 서열을 알고 있었고, 그 단백질의 염기서열을 코돈으로 번역하여 아미노산 서열을 찾아보았다. 하지만 실제로는 지난 글과 같이 '염기서열을 알고있는' 상태에서 찾는 것이 아니라, 염기 서열 안에서 유전자를 찾아야 하는 상황이 더 많다.만약 우리가 찾아야 하는 유전자의 염기 서열을 모를 때 유전자를 어떻게 찾을 수 있을까? 우리는 모든 유전자가 특정 코돈 (AUG) 으로 시작하고 특정 코돈들 중 하나 (TAA, TAG, TGA) 로 끝나는 것을 알고있다.그렇다면 개시 코돈과 종결 코돈만으로 유전..
FASTA : 생물학적 서열에 대한 공통 포맷 각 FASTA 문자열은 '>' 로 시작하는 header line 으로 시작한다.그 다음에는 여러 줄의 문자열 데이터가 들어오는데,DNA 는 ACGT 로 구성된 문자열이RNA 는 ACGU 로 구성된 문자열이단백질은 ACDEFGHIKLMNOPQRSTUVWY 로 구성된 문자열이 주어진다. 하나의 문자열은 또 다른 header line 을 만나거나 EOF 신호를 만나면 끝난다.따라서 하나의 FASTA 파일에는 여러 시퀀스가 존재할 수 있다.또한 각 시퀀스는 0-index 가 아니라 1-index 형태를 따른다. 예를 들어 SARS-COV-2Wuhan.fasta 파일을 보면 첫 줄에는 > 로 시작하는 헤더라인이 있다.그 다음줄에는 ATCG 로 구성된 DNA 염기서열..
