알고리즘3 k-mer로 패턴 빈도 구하기 Goal 1. K-mer란? 2. K-mer로 서열 패턴 빈도 구하기 K-mer란? 생물정보학에서 k-mer라는 말을 흔히 들어 볼 수 있다. K-mer란 쉽게 얘기해서 k 숫자만큼 길이를 가진 서열을 얘기한다. 예를 들어 3-mer라면 3 bp 길이를 가진 "ATA", "ATT", "GCT", "AGT" 등 3개의 염기로 이루어진 DNA 서열 같은걸 얘기하는 것이다. K-mer로 패턴 빈도 구하기 문제 DNA 복제를 시작하는 시점을 origin of replication, 즉 ori 라고 부른다. Vibrio cholerae라는 균의 ori 서열은 아래와 같다. atcaatgatcaacgtaagcttctaagcatgatcaaggtgctcacacagtttatccacaacctgagtggatgacatcaag.. 2023. 6. 14. 니들만-브니쉬(분쉬) 알고리즘 (Needleman-Wunsch) Goal 1. 니들만-브니쉬 알고리즘이란? 2. 니들만-브니쉬 알고리즘 알아보기 니들만-브니쉬 알고리즘이란? 두개의 DNA나 단백질 서열이 있을 때 sequence alignment를 하기 위한 알고리즘이다. Alignment란 쉽게 말해서 두 서열이 어떤 부분에 매치가 되고 어떤 부분엔 매치가 안 되는지 보여주는 것이다. 예를 들어 ATGCA와 ATCG를 align 한다면 아래와 같이 정렬할 수 있다. ATGCA AT-CG 최대한 매치되는 부분을 맞추고 매치가 되지 않는 부분은 하이픈(-)으로 표시하며 이걸 "gap"이라 부른다. 이런식으로 두 서열이 매치가 얼마나 잘 됐는지 판단하는 기준으로 alignment score를 사용하게 되는데 매치가 되면 플러스 값을 부여하고 매치가 되지 않거나 gap이 .. 2023. 6. 14. 다이나믹 프로그래밍 (Dynamic Programming) Goal 1. 다이나믹 프로그래밍 이해하기 2. Top-down과 bottom-up 방법 알아보기 다이나믹 프로그래밍(Dynamic Programing)이란? 다이나믹 프로그래밍이란 어떤 문제가 주어졌을 때 그 문제를 더 작은 단위의 문제들로 쪼개서 작은 문제부터 풀어나가는 방법이다. 더 작은 단위로 쪼개진 문제를 풀어서 얻은 결과로 원래 문제의 해답에 점점 더 가까워지는 방식이다. 이 알고리즘의 헛점은 문제를 작은 단위로 쪼갤 수 있을 때만 사용할 수 있다는 것이다. 다이나믹 프로그래밍 알고리즘을 사용하는 가장 흔한 예제가 바로 피보나치 숫자이다. 피보나치 숫자는 그 전에 오는 두 숫자를 계속해서 더해 나가기 때문에 n번째 숫자를 알아내기 위해선 처음부터 계속 더해오면 된다. 두 숫자씩 더하는 작은 단.. 2023. 6. 13. 이전 1 다음
