10 601 Machine Learning Computational biology Sequence alignment and profile HMMs Central dogma DNA CCTGAGCCAACTATTGATGAA transcription mRNA CCUGAGCCAACUAUUGAUGAA translation Protein PEPTIDE 2 Growth in biological data Lu et al Bioinformatics 2009 3 Central dogma Can be measured using sequencing techniques Can be measured using microarrays DNA CCTGAGCCAACTATTGATGAA transcription mRNA CCUGAGCCAACUAUUGAUGAA translation Protein Can be measured using mass spectrometry PEPTIDE 4 5 FDA Approves Gene Based Breast Cancer Test MammaPrint is a DNA microarray based test that measures the activity of 70 genes in a sample of a woman s breast cancer tumor and then uses a specific formula to determine whether the patient is deemed low risk or high risk for the spread of the cancer to another site Washington Post 2 06 2007 Input Output HMM For Data Integration I g H H H H 0 1 2 3 O O O O 0 1 2 3 Active Learning 8 Assigning function to proteins One of the main goals of molecular and computational biology There are 25000 human genes and the vast majority of their functions is still unknown Several ways to determine function Direct experiments knockout overexpression Interacting partners 3D structures Sequence homology Hard Easier 9 Function from sequence homology We have a query gene ACTGGTGTACCGAT Given a database containing genes with known function our goal is to find similar genes from this database possibly in another organism When we find such gene we predict the function of the query gene to be similar to the resulting database gene Problems How do we determine similarity 10 Sequence analysis techniques A major area of research within computational biology Initially based on deterministic or heuristic alignment methods More recently based on probabilistic inference methods 11 Sequence analysis Traditional Dynamic programming Probabilsitic Profile HMMs 12 Alignment Possible reasons for differences Substitutions Insertions Deletions 13 Pairwise sequence alignment ACATTG AACATT A AGCCTT AGCATT C A T T G A A C A T T A G C C T T A G C A T T 14 Pairwise sequence alignment AGCCTT ACCATT A G C C T T We cannot expect the alignments A C to C be A perfect T T AGCCTT But we need to determine what is the reason for the difference AGCATT insertion deletion or substitution A G C C T T A G C A T T 15 Scoring Alignments Alignments can be scored by comparing the resulting alignment to a background random model Independent Related P x y I qxi qx j i Score for alignment j i S s xi yi i P x y M pxi yi where pa b s a b log qa qb Can be computed for each pair of letters 16 Scoring Alignments Alignments can be scored by comparing the resulting alignment to a background random model Independent In other words we are trying to find Related an alignment that maximizes the likelihood ratio of the aligned Ppair x y compared I qx toqxthe background P x ymodel M px y i j i Score for alignment i i j S s xi yi i i where pa b s a b log qa qb 17 Computing optimal alignment The Needham Wuncsh algorithm F i 1 j 1 s xi xj F i j max F i 1 j d d is a penalty for a gap F i j 1 d A G C C T T A C C A T T F i 1 j 1 F i 1 j F i j 1 F i j 18 Example Assume a simple model where S a b 1 if a b and 5 otherwise Also assume that d 1 0 A 1 C 2 C 3 A 4 T 5 T 6 A G C C T T 1 2 3 4 5 6 19 Example Assume a simple model where S a b 1 if a b and 5 otherwise Also assume that d 1 F i 1 j 1 s xi xj F i j max F i 1 j d F i j 1 d A G C C T T 0 1 2 3 4 5 6 A 1 1 C 2 C 3 A 4 T 5 T 6 20 Example Assume a simple model where S a b 1 if a b and 5 otherwise Also assume that d 1 F i 1 j 1 s xi xj F i j max F i 1 j d F i j 1 d A G C C T T 0 1 2 3 4 5 6 A 1 1 0 C 2 0 C 3 A 4 T 5 T 6 21 Example Assume a simple model where S a b 1 if a b and 5 otherwise Also assume that d 1 F i 1 j 1 s xi xj F i j max F i 1 j d F i j 1 d A G C C T T 0 1 2 3 4 5 6 A 1 1 0 1 2 3 4 C 2 0 1 C 3 1 A 4 2 T 5 3 T 6 4 22 Example Assume a simple model where S a b 1 if a b and 5 otherwise Also assume that d 1 A G C C T T 0 1 2 3 4 5 6 A 1 1 0 1 2 3 4 C 2 0 1 1 0 1 2 C 3 1 2 0 2 1 0 A 4 2 3 1 1 0 1 T 5 3 4 2 0 2 1 T 6 4 5 3 1 1 3 23 Example Assume a simple model where S a b 1 if a b and 5 otherwise Also assume that d 1 A G C C T T 0 1 2 3 4 5 6 A 1 1 0 1 2 3 4 C 2 0 1 1 0 1 2 C 3 1 2 0 2 1 0 A 4 2 3 1 1 0 1 T 5 3 4 2 0 2 1 T 6 4 5 3 1 1 3 24 Example Assume a simple model where S a b 1 if a b and 5 otherwise Also assume that d 1 A G C C A T T C C A T T A G C C T T 0 1 2 3 4 5 6 A 1 1 0 1 2 3 4 C 2 0 1 1 0 1 2 C 3 1 2 0 2 1 0 A 4 2 3 1 1 0 1 T 5 3 4 2 0 2 1 T 6 4 5 3 1 1 3 25 Running time The running time of an alignment algorithms if O n2 This doesn t sound too bad or is it The time requirement for doing global sequence alignment is too high in many cases Consider a database with tens of thousands of sequences Looking through all these sequences for the best alignment is too time consuming In many cases a much faster heuristic approach can achieve equally good results 26 Sequence analysis Traditional Dynamic programming Probabilsitic Profile …
View Full Document
Unlocking...