Algorithms in bioinformatics (CSI 5126)=1Please don't print these lecture notes unless you really need

1Algorithms in bioinformatics (CSI 5126)Marcel Turcotte(turcotte@site.uottawa.ca)School of Information Technology and EngineeringUniversity of OttawaCanadaOctober 16, 20091Please don’t print these lecture notes unless you really need to!Marcel Turcotte (turcotte@site.uottawa.ca) CSI 5126. Algorithms in bioinformaticsSmith & WatermanBase conditions,v(i; 0) = 0;i2 0::nv(0;j) = 0;j2 0::mGeneral case,80;> v(i;j 1) +d;:v(i 1;j 1) +s(S (i);S (j)):1 2where d is the cost for a deletion/insertion, while s(a;b) is thesubstitution score.Solution,?v = max[v(i;j) : i n;j m]) Smith & Waterman (1981) J. Mol. Biol. 147:195-197.Marcel Turcotte (turcotte@site.uottawa.ca) CSI 5126. Algorithms in bioinformaticsProbabilistic FrameworkI Recall that a sequence alignment should answer the question:\are the two sequences (evolutionary) related?"I In other words, is the observed sequence alignment the resultof:1. an evolutionary process, where both sequences have evolvedindependtly from a common ancestry, or2. can it be attributable to chance alone; randomly selecting twounrelated sequences could produce a similar alignment score.Marcel Turcotte (turcotte@site.uottawa.ca) CSI 5126. Algorithms in bioinformaticsProtein sequence probabilitiesIt’s useful to consider a \simple" probabilistic model of a proteinsequence, given p , the probability of observing the amino acid a,asuch that,p > 0a20Xp = 1aa=1Let’s de ne the ...