지능형생물정보학

01 Where in a Genome Does DNA Replication Begin?

1-1

• oriC: DNA에서 복제의 시작점
• k-mer: mer은 polymer할 때 mer
• most frequent k-mer: 길이 k의 text중 가장 frequent한 text
• kmer 찾는것이 실제로 hidden message를 찾는것에 의미가 있는가? (15p)
• polymerase: polymer를 만드는 애
• dnaA: replication initiater
• dnaA box

• 19p: 초록색과 빨간색은 complementary한 관계에 있다
• 염기서열의 첫부분은 5’ end 끝부분은 3’ end라고 함
• 5’ end가 항상 왼쪽으로 오게 쓴다
• genome(또는 생물 종류)에 따라 hidden message가 다를 수 있다

• oriC가 주어질 때는 hidden message를 찾을 수 있지만 전체 genome에서 oriC를 찾으려면?
• oriC크기의 window를 잡아서 해당 window내의 frequent word를 찾아서 window끼리 비교한다

1-2

Probabilities of Patterns in a String

• Pr(4, 2, “11”, 2) > Pr(4, 2, “01”, 2) 인 이유는 11은 overlap이 가능하기때문이다 (111이면 11이 두번 있는셈)
• 6쪽의 공식은 overestimate임. 왜냐하면 예로 0101011이라는 string은 0101xxx, xx0101x 등 중복되어 counting 될 수 있기 때문이다
  

Finding Frequent Words

• brute force
• less time: frequency array
• patternToNumber, NumberToPattern -> O(k)
• findingFrequentWordsBySorting -> O(1)
• total -> O(text * k)
• 4의 k승만큼의 메모리를 사용
• sorting을 추가한다면? findingFrequentWordsBySorting -> 단어길이만큼의 메모리를 사용
• k가 길경우에는 sorting을 사용하고 짧을경우에는 sorting없이 그냥 하는것이 나음

Finding Clumps

• index를 integer로 바꾸는것 -> text * k

1-3

• dna 복제는 2개 방향으로 밖에 진행될 수 없다(bidirectional)
• 갈라지는동안 okazaki fragment가 부분적으로 복제된다
• 그리고 마지막에 합쳐짐
• 방향(forward, backward)에 따라 mutation rate가 다름
• single-stranded DNA has a much higher mutation rate than double-stranded DNA
• cytosine rapidly mutates into thymine through deamination & deamination rates rise 100-fold when DNA is single stranded
• skew diagram
• skew(k): |G| - |C| for the first k nucleotides of genome(누적함수)
• skew 함수가 감소하다가 증가하는 부분이 oriC라고 추측할 수 있다

1-4

• Hamming Distance Problem
• hamming distance: number of mismatches between string p and q
• d-neighborhood: hamming distance가 d보다 작거나 같은 k-mer들
• skew diagram에서 감소-증가 바뀌는 부분이 반드시 oriC라고 할 수 없다. reversal때문에 genome이 부분적으로 바뀔 수 있기 때문

//Assignment 1

Rosalind - bioinformatics problems - overlap graphs

• fasta format: 헤더와 스트링이 있는 포맷

04 How Do We Sequence Antibiotics?

• Searching for Tyrocidine B1
• Translation은 genome의 어느 부분에서든 시작해도 된다
• Cyclic
• DNA->RNA
• Transcription 과정
• RNA Polymerase에 의해 진행됨
• RNA->Protein
• Translation 과정
• Ribosome에 의해 진행됨
• 하지만 ribosome이 억제됐을 때 합성되는 단백질도 있음. NRP synthetase에 의해 합성되는 tyrocidine
• Mass Spectrometer로 분자의 질량을 계산 -> 어떤 단백질인지 알아냄
• 1 Dalton = mass of proton/neutron
• mass of molecule = sum of protons/neutrons
• 단, 20개 아미노산 중 정수로 따질 경우 같은 질량을 가진 애들이 2쌍 있음 -> 18가지의 질량을 구분할 수 있음
• Mass Spectrometer
• 1. Theoretical spectrum을 구함
• 길이 n의 주어진 peptide를 순서에 따라 쪼개서 가능한 모든 subpeptide(1~n-1)의 mass를 구함
• 2. spectrum에 해당하는 peptide를 찾는다(Cyclopeptide Sequencing Problem)

—

• A Brute Force Algorithm for Cyclopeptide Sequencing
• 주어진 mass를 가지는 모든 가능한 peptide sequence를 생성하여 비교함
• 결론적으로 불가능하다. 왜냐하면 가능한 sequence의 수가 exponentially 증가하기 때문에
• 해결책: branch-and-bound
• Cyclopeptide Sequencing with Branch-and-Bound
• 주어진 spectrum중 57~186에 해당하는 mass를 골라 가능한 1-mer들을 구한다 -> 해당 1-mer들로 만들 수 있는 가능한 2-mer를 만든다 -> 2-mer들 중 spectrum과 일치하는 것들만 남긴 후 3-mer를 만든다 -> 반복
• 어떤 dataset에 대해서는 exponential 할 수 있지만 보통의 상황에서는 굉장히 빠름(증명되지는 않음)
• Adapting Sequencing for Spectra with Errors
• 실제 spectrum에는 error가 있을 수 있음. 있어야 할 mass가 없거나 없어야 할 mass가 있을 수 있음
• false masses: present in experimental spectrum, absent from theoretical spectrum
• missing masses: present in theoretical spectrum, absent from experimental spectrum
• 해결책: theoretical, experimental spectrum에 공통적으로 해당하는 mass만 추림 + LeaderboardCyclopeptideSequencing
• LeaderboardCyclopeptideSequencing
• 주어진 spectrum에서 정확한 1-mer들을 추려낼 수 없기 때문에(에러 가능성) 18개의 아미노산 mass 모두에 대해 따짐
• low-scoring peptide를 쳐냄(단, keep top N with ties)
• candidate이 없을 때까지 extend, cut 반복
• heuristic한 방법이기 때문에 precise하지 않고 correct solution을 miss할 가능성이 있음(진작에 쳐내진 branch 중 정확한 솔루션이 존재할 가능성)
• 실제 실험 결과 10%의 error가 있을 경우 제대로 찾았지만, 25%의 error가 있던 경우에는 정확한 답을 찾지 못함
• From 20 to More than 100 Amino Acids
• 실제 아미노산 중에서는 mass가 일정하지 않은 non-standard amino acid가 존재한다(Ornithine)
• 따라서 18가지의 mass말고 그냥 57-186에 해당하는 정수로 따지면 리더보드 알고리즘으로 10%의 에러가 있을 경우에도 제대로 답을 찾지 못함
• The Spectral Convolution Saves the Day
• 주어진 spectrum에서 어떤 mass pair의 차는 1-mer의 mass에 해당할 수 있음. 물론 아닐 수도 있음 => Spectral Convolution!
• 모든 mass pair의 차를 구해서 테이블에 나타냄
• 테이블을 보면 여러번 나오는 mass가 있을 것. 실제 spectrum에 해당하는 1-mer일 가능성이 높다
• ConvolutionCyclopeptideSequencing
• 주어진 sequence에 대해 spectral convolution을 진행 -> M most frequent mass에 대해 LeaderboardCyclopeptideSequencing을 진행
• 실험 결과 M=10일 경우 10%의 error, 25%의 error 두 경우에 대해 모두 제대로 나옴
• The Truth About Spectra
• 실제 mass spectrometer에서는 25%보다도 더 많은 에러 가능성이 있다…실제 스펙트럼은 100개인데 1000개가 나올수도 있음
• Beltway and Turnpike Problems
• 두 문제 모두 polynomial한 알고리즘이 밝혀지지 않음
• turnpike의 경우에는 pseudo-polynomial한 알고리즘은 증명된 바 있음
• 점의 개수에 대해 polynomial한게 아니라 segment의 길이에 대해 polynomial함

05 How Do We Compare Biological Sequences?

• From Sequence Comparison to Biological Insights
• sequence alignment의 중요성
• 길이가 다른 여러개의 sequence를 앞/뒤나 중간에 띄워놓아서 sequence간의 공통 부분을 찾아내는 것
• Cystic Fibrosis
• The Alignment Game and the Longest Common Subsequence
• dynamic programming을 이용하여 해결해야 함. genome의 크기가 크기 때문에
• 두개의 스트링을 비교하며 맞을 경우 match, 안 맞을경우 mismatch, 빈 공간을 넣을 경우 insertion 처리
• 하나의 스트링 입장에서 insertion은 다른 스트링에서의 deletion
• Longest Common Subsequence Problem이 됨.
• Input: 두개의 스트링
• Output: A longest common subsequence of these strings(unique 하지 않음)
• The Manhattan Tourist Problem
• Longest Path in a Directed Graph Problem(irregular grid)
• The Change Problem
• Input: integer money & array of positive integers(돈의 단위)
• Output: minimum number of coins with denominations(단위) that changes money
• Greedy 알고리즘을 사용하면 최적의 해가 되는 경우가 있음(우리나라 단위 시스템의 경우)
• 안되는 경우 Recursive한 방법을 쓰면 됨. 하지만 이 경우에는 동일한 항목에 대한 계산을 여러번 하게 된다는 문제점이 있음
• 해결책: 다이나믹 프로그래밍 - 한번 계산한 항목을 저장
• biology에서는 평균적으로 alignment가 잘 맞는것 보다 local하게 alignment가 완벽하게 맞는것이 더 중요할 때가 많다
• homeobox genes
• gap penalty
• multiple sequence alignment
• 비교해야 하는 sequence의 개수가 증가할수록 시간이 exponential하게 늘어나기 때문에 exact한 답을 구하기는 거의 불가능하고 approximation 할 수밖에 없음 - suboptimal solution
• profile을 이용
• asymptotic: 점근선의

05 How Did Yeast Become a Wine-Maker?

• Which Yeast Genes Are Responsible for Wine Making
• diauxic shift: yeast가 자신의 metabolism을 바꾸는것(glucose를 먹고 살다가 주변에 없으면 ethanol을 먹고삼)
• diauxic shift가 발생하기 이전, 당시, 이후에 yeast의 gene expression을 관찰 -> 비슷한 behavior의 gene들을 clustering함
• clustering
• k-center clustering problem
• noise에 민감함
• 해결방법: maximal distance 기준으로 center를 정하던 것을 squared error distortion 기준으로 수정 => k-means clustering problem
• 하지만 k-means의 문제점 -> NP-Hard for k>1임 따라서 approximation을 하여 suboptimal solution을 구함
• lloyd algorithm
• k-means clustering 알고리즘
• 항상 converge함
• hard/soft clustering
• soft clustering: clustering with responsibility
• stiffness parameter를 통해 hard clustering-soft clustering의 정도를 조절할 수 있음
• From Coin Flipping to k-means Clustering
• clustering은 em(expectation-maximization) 알고리즘의 일종
• Hierarchical clustering
• k가 주어질 필요 없음

00 EXT

02 Motif finding

• greedy approach
• randomized approach
• gibbs sampling
• expectation-maximization

03 Graph for string reconstruction: Assembly

• overlap graph
• de Bruijin graph
• hidden Markov model for gene finding

04 Structural variations

• insertion/deletion
• translocation

—

• metagenomics
• string match
• genotype(유전형) vs phenotype(표현형)
• DNA sequencing
• sequencer를 이용하여 할 수 있다
• 실제 dna에서 ACGT string을 얻어내는 과정
• Assembly
• 100~200개 되는 base pair를 이어 붙이는 과정
• 현재 기술으로는 sequencer가 모든 dna를 처음부터 끝까지 읽지 못하기 때문에 조각조각 읽어 붙이는것임
• Motif finding
• Text mining for biomedical literature
• 실제 literature를 train하여 어떤 term과 어떤 term이 관련 되어 있는지 알아냄.

<How do we find motifs?>

• motif: 반복되는 string
• k-mer = k-word = k-gram
• (k, d)-motif: k-mer that appears in each sequence with at most d mismatches
• consensus: 각 인덱스에서 가장 빈도수가 높은 애들의 string
• consensus의 conservation 정도를 측정하기 위해 entropy를 사용한다
• entropy가 높을수록 conservation 감소
• EM(expectation maximization)
• k-means와 방식이 비슷함: 실제 데이터를 반영한 모델을 만듬 -> 모델과 데이터를 비교 -> 업데이트 -> 반복
• 20쪽: 그대로 implement하면 두가지 문제가 발생
• 0이 하나라도 있으면 0이 됨 => pseudocount 개념 도입
• 확률에 로그를 취해줘야함
• randomised motif search
• global max를 보장할 수 없기 때문에 여러번 시행함(local max를 여러번 구해서 비교)

<Expectation Maximization>

• 어떤 데이터가 어디에 속하는지(classification)하기 위해서는 모델을 만들어야 한다
• 모델을 만드는 가장 간단한 방법 -> normal distribution
• class 정보가 주어지지 않을 경우: EM을 사용하여 hidden variable/parameter를 estimate
• naive bayesian classifier
• 한 개체가 하나의 cluster를 정하는 데에만 사용되는 것을 hard clustering이라고 함 => 결과가 extreme해질 가능성이 존재
• 하나의 개체에 대해 어떤 cluster가 될 “확률”을 계산하면 됨 = soft clustering
• 20쪽 k-means clustering은 hard clustering의 예이다
• soft clustering: EM for Gaussian mixture

<Gibbs Sampling>

• randomized motif search와 다른점
• randomized motif search may replace all k-mers in a single iteration
• gibbs sampling replaces a “single” k-mer at each iteration -> sampling with more caution
• relative entropy
• background probability 개념을 이용
• minimize the entropy of a motif matrix
• maximize the relative entropy
• “은/는”, “~이다” 와 같이 많이 등장하지만 중요한 의미를 갖지 않는 string을 처리하기 위함

<Assembly Problem>

• overlap graph를 만들면 쉽게 해결할 수 있음
• a의 prefix와 b의 suffix가 같으면 edge로 연결
• 모든 node를 딱 한번씩만 방문하는 path를 찾는 문제가 됨(Hamiltonian path problem)
• k-mer 자체를 node에 대응시키지 않고 edge에 대응시킴 => de Bruijn graph
• node는 edge의 prefix(TAA일 경우 앞의 노드는 TA, 뒤의 노드는 AA)
• 노드의 중복을 허락하지 않음(중복이 나올 경우 합침)
• Eulerian path problem이 됨(모든 edge를 한번씩 거침)
• Eulerian graph: eulerian cycle이 존재하는 graph
• Eulerian cycle: balanced & strongly connected
• 실제로는 k를 보통 50으로 잡아서 해결한다
• 너무 짧을 경우: 중복 edge가 많이 발생
• 너무 길 경우: 한 node의 크기가 너무 커짐 -> 메모리 이슈
• edge 여러개일 경우 해결법
• node간 edge가 여러개일 경우에 어떤 edge를 선택할까 하는 문제가 발생하게 됨. 그런 경우에는 k+1 mer 그래프를 그림. unique path가 생길 때까지 k를 늘려간다
• paired composition
• 방향을 양쪽으로 해서 읽으면 뒷부분에 대한 정보가 추가적으로 생김 => 어떤 edge로 이동할 지 priority를 정해줄 수 있음
• maximal non-branching path
• 노드간 edge가 여러개인 경우 그냥 그래프를 따로 나눈다. => 결과로 나온 여러가지 그래프를 실험적으로 맞춰봄

<Hidden Markov Model(HMM)>

• Markov chain
• trainsition probability를 고려한 모델
• inhomogenous Markov chain
• different distributions at different positions in the sequence
• ex) DNA sequence에서 맨 처음 위치에는 A가 올 확률이 높고 두번째 위치에는 낮고… 등등 이러한 정보를 반영
• MLE(Maximum Likelihood Estimators)
• CpG island
• ~ island: ~가 많이 있는 부분을 비유적으로 의미함
• dna 서열에서는 보통 gene이 등장하기 전에 CpG island가 많이 있음
• Hidden Markov Model
• state, state 내의 symbol, transition probability, emission probability를 정의한다. 어떻게? 데이터를 학습시켜야함!
• 어떤 종류의 problem을 해결할 수 있을까
• how likely is a given sequence?(forward algorithm)
• 길이가 같은 sequence들의 모든 조합 중 특정 sequence가 나올 확률(결론적으로 state를 고려함)
• what is the most probable path for generating a given sequence?(viterbi algorithm)
• 어떤 sequence가 주어졌을 때 그 sequence의 state 변화를 예상
• how can we learn the hmm parameters given a set of sequences?(forward-backward(baum-welch) algorithm)
• viterbi algorithm은 꽤 fair하게 state변화를 감지 할 수 있지만 정확하게는 감지할 수 없을수도 있다. 따라서 이런 경우에는 state 모델을 잘 설계하는것이 효율/성능을 높일 수 있다.

<How Do We Locate Disease-Causing Mutations?>

• Combinatorial Pattern Matching
• genotype-phenotype(표현형)간 관련성을 연구하는 것이 중요
• read mapping: reference genome에서 어떤 부분이 read와 대응되는지 찾는 것
• Trie: 그래프 자료구조의 일종
• store pairs of keys and data
• represent a collection of strings whose edge has a character
• suffix tree: trie를 compression한 것
• burrows-wheeler transform
• genome을 run-length encoding이 가능한 형태로 만드는 transform
• run-length encoding: aaaabbbccc -> 4a3b3c