The GRAIL Gene Finding Program

The most popular gene finding program is GRAIL.
GRAIL can be accessed at http://avalon.epm.ornl.gov/Grail-bin/EmptyGrailForm.
GRAIL works by using a neural network to combine the information from various gene finding signals:
- A neural network is an elementary model of the behavior of neurons.
- Each neuron is assumed to combine information in a linear fashion and then apply some non-linear function f:
  
  O = f(a₀ + a₁ I₁ + ... + a_m I_m)
- The parameters a_i can be learned by using variants of "Hebbian" learning:
  
  If on some example O_i is correct and I_i is positive, increase a_i and vice versa.
- Neurons can combined in a network to calculate some function:

KMP.htm100644 5736 106 5437 6461114177 11112 0ustar attesoncbil The Knuth-Morris-Pratt Algorithm

The Knuth-Morris-Pratt Algorithm

The Knuth-Morris-Pratt algorithm builds a failure function for the pattern. Consider again the pattern p=AAATA::
Consider again searching in the text t=AATAAAATA: A A T A A A A T A A A T A A A A T A A A T A A A A T A A A T A A A A T A A A T A A A A T A A A T A A A A T A A A T A A A A T A A A T A A A A T A A A T A A A A T A A A T A A A A T A
The Knuth-Morris-Pratt algorithm always requires around n+m operations in the worst case where m is the length of p and n is the length of t.

A	A	T	A	A	A	A	T	A

A	A	T	A	A	A	A	T	A

A	A	T	A	A	A	A	T	A

A	A	T	A	A	A	A	T	A

A	A	T	A	A	A	A	T	A

A	A	T	A	A	A	A	T	A

A	A	T	A	A	A	A	T	A

A	A	T	A	A	A	A	T	A

auto.gif100644 5736 106 2644 6460670652 11411 0ustar attesoncbilGIF89a¾«ðÿÿÿ!ù,¾«þ„©Ëí£œ´Ú‹³Þ¼û†âH–æ‰¦ê ¶î ÇòL×öçúÎ÷þ ‡Ä¢ñˆL*—Ì¦ó J§'ªõŠÍj·Ü®÷ ‹Çä²ùŒN«×ì¶û ËçtEàŽÏëóõ¾?ºwwðgx¸£w¢ˆØèˆÂ ùHY9(ˆƒg¹Éi‡Ù£Ù)Ú:T:Š÷‰´šêzvºûJÛ' u[«K•+'» ¬ôË[lœ4|•|Ì|³œõÜ,íR ;}Mm[Ý¢ î=^ÁýfNž®~®îŽ!nÿNÎNgOŸ€¯ïo0MÀºø2HÂƒ Ç-<ô°á«ˆ%J£ˆ£EþK3nÖ‘'ÇZ!• §ÚI“(9[ùfK4“šÉœY¦¦Mœ÷\»Éó‹Ol@ƒnaä¨Q,³ˆ. ˆÚ@ZJŸ‚È5uBT&[e õŠTØW#˜¶fu€µêŠ´ÈØÁ–•[µ‹Î8Â Ýºhèõû`¯‰¿¦ðöÝb¡à¼‹P\2É@^66Ü!¢ãš KØì¡³-? u¾‰ô†'PËµ¦ zk¦]Ë´‡ûµ±3ä^-^‚®˜ió>nœ5L|ÌkôjŽ|Æó-¥ÿF`ñpç×wG—q«¶ñ¾w +÷y¸éÍGßªº÷líkŸoýyüÛþWªÏžOÿÙÇ€îHŸ-oQ È_€Š¸……þ!8!nÈa‡bœ‡"ŽH"V †XbŠ*†µƒ+¾˜"ˆžÀH£ˆ.-XÞŒ&8!Š;&Ø£ŽòÈ‡|-Y¤C"©‰…÷a÷ä 2-™Ÿ9K.Y%•'·%ZB¹à :]‰`–x å…Z¢" 'Z¡˜ëÁù¥œaF ¦uo~ÙæplâyÙrØé·JŸ° ªR¡ºíC(7†j…b™ ¢ÉÙ–Ùl¥ijÜ¡•q:©§“*¤£™ºh`ž]vêgv««-6+u‘ÉÚªª¯I¦a·":™®¿ÚJ–°»êªþV\~Ý%Wˆm9Û¬›¿Æ%!\'‹ri»,·£½4'[mØ¸£ã3mì->ë…íkè-û»¼×9z¥aÌ^àð¿·q|ïÎ¬^kð Eü`-3î¼æ°öÛT?Þî .ðÜÜ §ŠÍ)ß5úÜ©¯5ûbº¿ü-$_ óò ¿'ù§»öýûÿ¿™|`?C?žpp D\o÷ÀÄ$° ö‹ éò7ÁnT°!´à ú×A~N}!aåjgBúŒ¯„)lYðXØBÀ½.ƒ8a*lÃ¶‡9„ {BÃ-CdßíVDùM$Gìá"’ˆ-'š Ší¢â€—D)Ž‹÷h¢sÀEäyñ‹ #YÌHÆ ‘6kL#Ûè%7’"Œ¸ £‘Ç‘åñŽÄ°#æüÈGJ„/. ¤BÉ‚ï’-äB˜»Y»i’”¬¤%/‰ÉLjr“œì¤'? PŠr”¤,¥)O‰ Tªr•¬l¥+_ ËT;auto1.gif100644 5736 106 2666 6460670652 11476 0ustar attesoncbilGIF89a¾«ðÿÿÿ!ù,¾«þ„©Ëí£œ´Ú‹³Þ¼û†âH–æ‰¦ê ¶î ÇòL×öçúÎ÷þ ‡Ä¢ñˆL*—Ì¦ó J§'ªõŠÍj·Ü®÷ ‹Çä²ùŒN«×ì¶û ËçtEàŽÏëóõ¾?ºwwðgx¸£w¢ˆØèˆÂ ùHY9(ˆƒg¹Éi‡Ù£Ù)Ú:T:Š÷‰´šêzvºûJÛ' u[«K•+'» ¬ôË[lœ4|•|Ì|³œõÜ,íR ;}Mm[Ý¢ î=^ÁýfNž®~®îŽ!nÿNÎNgOŸ€¯ïo0MÀºø2HÂƒ Ç-<ô°á«ˆ%J£ˆ£EþK3nÖ‘'ÇZ!• §ÚI“(9[ùfK4“šÉœY¦¦Mœ÷\»Éó‹Ol@ƒnaä¨Q,³ˆ. ˆÚ@ZJŸ‚È5uBT&[e õŠTØW#˜¶fu@¨©¬UW°EÆîlŒ·E^Æ}9"ÎµÚBê{Ä ßE€M,¬ToX¨“Xè8oãº“ï« TñØ#_'jX‚ç—¾©¹«Œ£9°¶ Èë'—)’™v!Ø ìµÞà›Áïu½7Ï|Áq ·Ë'^—[o^øªOO®¼ÁråØà}îýºpíä³¡kÎü¥¨·w_o¼» ñÇ¿7gÝ¾yøãþåÏ-…^vý·[{ªÍÇÞ€î§H} ÎP`y"è“ƒvØá…"°áz ’Zˆ"Ž(Ý…‡yBbŠ*.v¢z£Š¢c©-x—:–ˆ¢‚Èè-ƒ|äˆ† "—‘ÎØ›’ r×'vP>©¡‹—T ˆ þÇŸ‰VJIc“^&yŸ˜rè¤™h¶¸&ƒáå—– ¹™$þáç%‚ú…×&ŸúçgžÿíÉ¦‹`rxž•tè¡JŸ°˜¢Žrshl/NÚ'(Pž©w®Ré¢Š’‡[Š¼UÆ™s²©šªm©¾†Úˆ¡¡ºªh³Š —«žvUˆ”áz+“µ,¡šŽºþfbšF,‚1‹´Â"†lmm)wÙz²mqÝ"JÖ‹ÚVK`d™{.¤éîºPÙÅˆ\ñè,»Ý„*™t¹äZŸâÛÀ!Lš»&lÉÙyöîä‹(ý‚RºÆLÚ(ìÉ;p2 C± ûBÆ-u¦ÇS| 2£—-·°v%ï‚²k‘«ÛË?ÚŒkÌ\èLÜÌ4KŠó”"«¤/&ß,« <[±4<Ç4=HF}rAS3Ü°ÏYOuz©tÍ*×U€-íÖ?í0Ú ©ÍÛkC‰È9-",¹ Ý®V„·;zkõ÷Ÿvÿ¸®sN«?ˆ›’2-Þä Kþ>-áLQÞ+S(a^yœû84Ÿ_ Orópº)£sk'ê¬åºšÃ.úQVzùØ± j'î=ê›:µ·gªEðüÖ=<ïÅÿóÂ'ïm8Î»6=Ä-G+F-,hß÷õ {-ò"Üî}ä°„Oýø øÎ‹¶ñì{¤Š©ª”Ïü÷êþóù/3¶€›¨ž Ø;F™c`øP‚£ é,˜/ &Nƒäàë<˜þaLèžC…õ`aHÂq†1ìÜí\H8n£†‰-aîxh½Öùp$4DE" QˆKT]{÷Ä "QÌD’½§¾¯qŠR¹È!˜E“l‘‹JrEÉ¨»/Þ ãÎÈFð¹‘sŒc»'x);’ŽÄ¨£-ÁG°àñ@_ IH— ò]L$G$¦ƒ9’(’TZ%'™z27˜ÄâŽüØÉPŠr”¤,¥)O‰ Tªr•¬l¥+_ ËX r–´¬¥-o‰Ë\êr—¼ìe- ;auto2.gif100644 5736 106 2660 6460670652 11471 0ustar attesoncbilGIF89a¾«ðÿÿÿ!ù,¾«þ„©Ëí£œ´Ú‹³Þ¼û†âH–æ‰¦ê ¶î ÇòL×öçúÎ÷þ ‡Ä¢ñˆL*—Ì¦ó J§'ªõŠÍj·Ü®÷ ‹Çä²ùŒN«×ì¶û ËçtEàŽÏëóõ¾?ºwwðgx¸£w¢ˆØèˆÂ ùHY9(ˆƒg¹Éi‡Ù£Ù)Ú:T:Š÷‰´šêzvºûJÛ' u[«K•+'» ¬ôË[lœ4|•|Ì|³œõÜ,íR ;}Mm[Ý¢ î=^ÁýfNž®~®îŽ!nÿNÎNgOŸ€¯ïo0MÀºø2HÂƒ Ç-<ô°á«ˆ%J£ˆ£EþK3nÖ‘'ÇZ!• §ÚI“(9[ùfK4“šÉœY¦¦Mœ÷\»Éó‹Ol@ƒnaä¨Q,³ˆ. ˆÚ@ZJŸ‚È5uBT&[e õŠTØW#˜¶fu€µê BM…¤EÆîlŒ·E^Æ}9Â ZHlÛþ-{0Ù {IàE 0ÄÂÂ†ûê²¸nÆy'»M áp‡ˆ”¯: ûW«)-—%tÞ¼OôMŒ§9|îêƒ5'r³)´ÎPH¶L{¼¡Ú÷2ƒÞÂÀN]ÜÎð-º]7Àw-o¶ÀƒÏèýy ì ‘£‹þœø‚ìÙ¾#§½²·øë±¨ç¶Î¾•úåÛÛk§_^þòõ2þ&å¾?Þyðì‡_|Š¸WÝXýE5_€õùDžƒùH „òWj¦'á]¯}bˆ¿i"b‰&~Øáx'®h"€ž°#ŠÝ x@Œ6~6w¾ˆ• #- ß‚ªØxá Y`Fæˆ¤’-8ƒþ§ÜŽJÖh¡æüøž‚Qê7c†néâ•cš‰¦˜ba•˜gÜŒ 2‰a IÂp²—dœ}¾Àš˜ùÉç•Q¹ŽqŸœ²¤H•rg"Šª´J£´½˜%Ü@Z)sè¡f›o"ÖFZh¡&gš§¡®V*d!Ž–ji–ÉšÙlœA™hD€(™®°Ö+°µE†k®eº…þã`ˆ){,©‚2(}j-X_p©x'Ù:©,]ŒYm¤dyî“ãŠë@CÉ5™µç²;Š¥&È«Ø]-P·ë¢ðº4½y‘Ëºš~gîN¾ˆn"- R¿ñB¸ï ~©Ë0I £ÚÄkiSpÃ §B"÷jL¤¿Ö\ r±N’| ËËšLÌ"ÈÌT´ív|¤Ë±ª</Áœ'¢ 4Ûâ³1CKìñÇÇí"V8íÜEE»õ›N¡ï'"TmuÖZo]×Â„]Ù›ˆ›:hÃ³vº_;ô4Kf¿"ö -ÍMOÝŽêí#ß§úã÷ßrÞ*à ÌAøÎ %Þî9Œû*-ã™Iþ>3åË~dùåò@3Sæáåäù³E,†'‰‰(@ "K‰µcbéè ':CŠðƒ-ŒÈŽE©Ü0‹Ö£¢±ÈÅ Q ŒaÌåçE.ž1xd,£)Úx.7þa¼“£IèH 8ÚxK÷˜Dà™¨ØûHÈ³²oƒLä ¹€9rqø’X%'YÅé“œì¤'? PŠr”¤,¥)O‰ Tªr•¬l¥+_ ËX r–´¬¥-o‰Ë\f ;auto3.gif100644 5736 106 2650 6460670652 11471 0ustar attesoncbilGIF89a¾«ðÿÿÿ!ù,¾«þ„©Ëí£œ´Ú‹³Þ¼û†âH–æ‰¦ê ¶î ÇòL×öçúÎ÷þ ‡Ä¢ñˆL*—Ì¦ó J§'ªõŠÍj·Ü®÷ ‹Çä²ùŒN«×ì¶û ËçtEàŽÏëóõ¾?ºwwðgx¸£w¢ˆØèˆÂ ùHY9(ˆƒg¹Éi‡Ù£Ù)Ú:T:Š÷‰´šêzvºûJÛ' u[«K•+'» ¬ôË[lœ4|•|Ì|³œõÜ,íR ;}Mm[Ý¢ î=^ÁýfNž®~®îŽ!nÿNÎNgOŸ€¯ïo0MÀºø2HÂƒ Ç-<ô°á«ˆ%J£ˆ£EþK3nÖ‘'ÇZ!• §ÚI“(9[ùfK4“šÉœY¦¦Mœ÷\»Éó‹Ol@ƒnaä¨Q,³ˆ. ˆÚ@ZJŸ‚È5uBT&[e õŠTØW#˜¶fu€µêŠ´ÈÁ–»·-^Î}9Â ZHö.rÛˆÞ#ƒMì{øj¿$2Î X§àÅE Á s‡ˆKèü!òØœ †ºOkêÍåPSÍAtWao¨Mzµj™öz»¶ÃÀö:BûˆOF0[7íàÌ—ã†‰/z^"›Ï î¶¸ñë¾`F'¼uñä³W¾û6óîæ[ùfÏÝ=ñBÙ§Çª¾ ¼øûëþÇW‰-räôž2Ì×_~6Ì‡`}í)‚pöùT ‚B¨ }ª'a€ÚÉbˆ"Zè¡ˆ&žh¢v¢Èb‹’‹2†Hâ]3ÞXpã˜ß‹úéHaMý($„Ém÷z·`T6b'dÀi8%‡L&våƒY ˆ%—Z"ç¤ H-ÈŸ^þ·%ŒjvˆæaK Ècšç™g¦9sr ¤’z†|ižÙgéÝyQ¹ ˜*BèkŠÂÈ(T“”Â'6’¸¤‹r"(eÏ±æèqª vâo§‰z*(-¢µª¥]6ª¤4Âš*ªˆMVZQ–±«) VF¯Á-·«R…Ëþ*Y¢v+²å-Z˜ZqvW[ *Ûc[Ù"ccR[)¸/*.¹ãJ -Pte–£¹ª2Å»¡UËÂµ²jªŽ¼"è{'h*$Gª'íä‹(ß&ã¹ÁðëY'a2Œ/Zþ± û¢"Àõj£ð.ÇæŠ&½i Y<“ÄËD*º.Ëq~lK *¯\ä<gà10[Y-p)þK±Ì r¼\4"GB-Kã²"OC= Î:×¨³ù'êž¨Î…ë‘o#9ÉJ[(é†—n*î¹ë.·ílû^\Â“)û~ÄO.ï>‘ü-÷u|É"'»¼â°œ|÷ºgŸwä+~3ôà" ŠéŸO6ûtºü’È¯5ý@Ûóõ é¿5þyùo1þ¡Âyô`ÿO4 Kø²K‚ßpà=,x þNƒ” 9¨<ÿ}„'+ ã¿úc„DQ!ß\¨ 6„…û#!¯dØÚ°_”Ã!Oª×B¶Nˆ–"¢ïtè $îð@ ™—H¦‹Q„O$C„¡HŒ)ÎK‹$¼¢*ªˆÅr‘|a¬ƒÆ2æ0¾£?sF'±ñi‹#WìHÇ>x,nÌc %®>úqc{|- iÆò²ˆ¤G»¶8¾F.G‡”¤%/‰ÉLjr“œì¤'? PŠr”¤,¥)O‰ Tªr•¬l¥+_ ËX r–Y(;auto4.gif100644 5736 106 2643 6460670652 11474 0ustar attesoncbilGIF89a¾«ðÿÿÿ!ù,¾«þ„©Ëí£œ´Ú‹³Þ¼û†âH–æ‰¦ê ¶î ÇòL×öçúÎ÷þ ‡Ä¢ñˆL*—Ì¦ó J§'ªõŠÍj·Ü®÷ ‹Çä²ùŒN«×ì¶û ËçtEàŽÏëóõ¾?ºwwðgx¸£w¢ˆØèˆÂ ùHY9(ˆƒg¹Éi‡Ù£Ù)Ú:T:Š÷‰´šêzvºûJÛ' u[«K•+'» ¬ôË[lœ4|•|Ì|³œõÜ,íR ;}Mm[Ý¢ î=^ÁýfNž®~®îŽ!nÿNÎNgOŸ€¯ïo0MÀºø2HÂƒ Ç-<ô°á«ˆ%J£ˆ£EþK3nÖ‘'ÇZ!• §ÚI“(9[ùfK4“šÉœY¦¦Mœ÷\»Éó‹Ol@ƒnaä¨Q,³ˆ. ˆÚ@ZJŸ‚È5uBT&[e õŠTØW#˜¶fu€µêŠ´ÈØA¨©¶E^º}9Â ZHö.ê{$®Î¹€M,¬t¡_ŠëFXœWðà¡-†€×CDÈWµ–Àùƒä±”=)´yŸær–)„æ€ñõ†-]}Ä.}[¦½Ýí0½î·ð"aæÁ{ðAª]7>\y^øªOO.=º ê>y?þ‚zëÙ-¡f¾’7ö:'kß-Ë}öòï‹k£½ðõðþ?ÀÈçÛuÝí $Q˜Àrã-ˆŸ}*Â`€ù-(€¦7ß]´}bˆn§œˆ&žžJ%¢Èb‹ºc‹®cµ(-‡ž4åàoîˆ'… 9â„|Ø'!}"X¤’GføÜ†³ÍX ’ Ryå„YnÙ${ñEˆŸ–VÙe*’ %tc’¸%|šcÞuo¶y™—>ržåÍ¹&›v^Ù‘†ðà¨"*=ZÀM)§ šqþ UWz–æh¡‰âÆšnRj§ E*boŸÚåc¥ Øéi©zZ¨~fªª©U¬h9†Y]¯Q+¥•%Ö*¯ÁÚ:¯£6þ¬¯ˆEVb[Í²rW[a-®t-6©´“‘-·ÅAû)v1òÖcI+—S¾s;×Æ Ý½ª|º7Äçü«E„›»†Ä txáò@3Sã1çþ$y²) JåˆjþàRœwÎæ‹[õ9è‚kQzâ¡§~_èV-É”èpÉNêë°CC8í¬ÚNóQº{l5ïž¨ü»"ÅÛÆzÞÄ§|2SÂ;¾<£ Cþ<âòL¿ ö¸Ww›ËpðÜ÷-PÎªŒ úªß6û'¸ß5üßÈ3ý%o{ò Ùo<ÿýû¯4ÆO€°-" h4æJ"À_ä˜ö„óc ÝáÀd‚Ž²ß9Ø &N„C wB1|„Ö#] [²Bª¼'1<Ø =wC''…ÆË!µ|(¼öAˆ<´è¾æ„ˆEt×EH@%z‰MôïGÅ*:#‹€à¢u ÅÁ]ñ‹óCÉH/fnŒhÜœ'FŽœ±‹oŒ£Ãæ.6ÚñÚ# -÷hÃ>Zñ€Iøø(³BjpZša¤"yg£:>r’”¬¤%/‰ÉLjr“œì¤'? PŠr”¤,¥)O‰ Tªr•¬l¥+_) ;auto5.gif100644 5736 106 2654 6460670652 11477 0ustar attesoncbilGIF89a¾«ðÿÿÿ!ù,¾«þ„©Ëí£œ´Ú‹³Þ¼û†âH–æ‰¦ê ¶î ÇòL×öçúÎ÷þ ‡Ä¢ñˆL*—Ì¦ó J§'ªõŠÍj·Ü®÷ ‹Çä²ùŒN«×ì¶û ËçtEàŽÏëóõ¾?ºwwðgx¸£w¢ˆØèˆÂ ùHY9(ˆƒg¹Éi‡Ù£Ù)Ú:T:Š÷‰´šêzvºûJÛ' u[«K•+'» ¬ôË[lœ4|•|Ì|³œõÜ,íR ;}Mm[Ý¢ î=^ÁýfNž®~®îŽ!nÿNÎNgOŸ€¯ïo0MÀºø2HÂƒ Ç-<ô°á«ˆ%J£ˆ£EþK3nÖ‘'ÇZ!• §ÚI“(9[ùfK4“šÉœY¦¦Mœ÷\»Éó‹Ol@ƒnaä¨Q,³ˆ. ˆÚ@ZJŸ‚È5uBT&[e õŠTØW#˜¶fu€µêŠ´ÈØÁ–¡·-^º}9Â ZHö.ê{Doà¹MA¼/ÄB¿$qL²)Â: '†€×CDÆŠµšò,dód •]ŽPè&FÎšËAu d5T"cMË–i/÷ëºc3èýÃ\×Ã± í3î#µk˜øš×èåü÷sàv°FMxf×1çž{ùŒ[ -”Ï ;;ÜXé¥Oo'ž· -å¿n<µøñ¥þÎW—¾R|ÿe•€ tçOr7_Ö=xàé7œ ùÉçßšgßiÜ-bˆ"b¥!o#žˆbmÄy¨aŠ.¢¡‰/Îèbxá-ˆ£ˆ¿AÇ"‡ž4…`_ þHb„šÜdƒ Æ8 V¸Ÿ…C-˜˜[=ÂFåŠ Þ—e—Vr¹¥—:)“]’y`‚D¹Þ'–àè”yæzî…©ež’¨G'žvŽY§Ÿ{î¨H¡*¾@Þ•˜)J7ý$zªén¹Y©o? Ræ £qr ›¦ ‡er©‚r"ª·µ&A¤ëœjê¢¡-œŽ¾‰V”d·Úú°¿"6i¿B¦þ”`d³Ášš±Á*«V\ƒ™Ø¶ri;x]ª-cl’u(¹aµu®\éNv)#t%8nq þ4…¬%X«‚·£µhïýþH¹‹Üéœ¥]T¯(ñæð Á %¬ð“ÿ¢•L…ÇL|o*çÎ»–6 ƒqc®Ih¤[Ç1I¼L$*¿ïNš'v¯ÌrËDÎã0–!±s^ ¯"j¾Æô,-B-\"C+=2"KCÜ4'K°" Ua4'¸$…u'VO5K_O“õUeg;6½]‹´ö;gðö³a§w /U7©åw?Vð-2þ .à@Ÿc¸¤%Ž-ã3…’ãð¤þ!ù 3Un-æŠiÞ(OwÆç‰pÞ 4¤g®Åé)ámúQVÁ™ºê;r!»µÇ*úž·£öz“¬‹utï¾ãíx i¿žûlyOŒðÎzÁ|Ç»ûèüóBE_4ömW/$,'Ûý=í"S2>©c—sðÜ¯ÚŒª¬Oùî$o”üõÀo7þˆê>ÿßØOÿ™€!`è3æOy1à(èÇ@ º„ÿ£ v,˜/ BDƒ Á` Ã–µ†W$c‹\uƒif:®v-°½ä6Q\#kÍzD[¨$½·#öÚ'úwî¿BÎâÍÛ¡_Š OXü¡qáÇ“ÛÌ(2‡Ì’˜v¦ ™Žço,Ç¬È-õgª´f½ú®Î‘®¼^Àôåx Â…6x»To±Áø&nvnÚÆ‘/8žœ†"ÜºwóK^¼O$'Ù_øa.¼»‹ïË£?‡´»ùßK»¡Ž¶|õç‰[‡->éiú þ¥ï_/œ}up ` ñíçÞóõ Vu >hY}ò a…†BLƒnèàp¶q¢ijb‰'€×„£•B-x2¼G"XèÝG!†3 è¡„ì)Xãt ¸[‚4®Øœ‹FjgŠŒGþ\’#êøbz¢xc€V*éß'By`Ö0ó¥sýQYd™Qæ˜Š ÝŽhZI¦›øY¨"‘Š0Âäu(j‚glwjÛžXú`ÌŸ…ÖVaDFç‚”'Z €Aú(¡ðuˆY¥”N*iŽ› ö©A•aêaŽq:ªª*”–^zØ‘zzz*©ÚºjœD'µ«l)*Oƒ_=×h©Â’uþ¬UÄ kT\½G'l_I‹,µVY;˜a|„õØ¯fµ¸S+Ã$‹B|»òÉm3Å¶•LU)<%É—à•L0-’æ¶å¬ —½—¥KBQðªÃo çB^Q]A3¯KõÂÄFj ‡-poOspÀÎ”ÆhÅ^z'å²~Éí³÷þóñ{—>Æó³PÿÏùksýýû¾k! Áx5âÏ€¯èŸóÀŽE-@]vÁ=ePNtà§@~yþcàáDJ …ï`á7£Â-Åx.ÄØ ³WCaäð…Ûa;|ÈCÂ™ˆA úŠˆ°òzH¤] •XD&þŠM”ÍrÆˆXÅE`qTÌ¢[¶è)zñw]ÄÇ8-GˆÛ;£ÖÈF–¸‘~sŒc÷W=;B-ø‚£-ýÅÇ(òó- IH¬™+2‹LäüLTGGJr’”¬¤%/‰ÉLjr“œì¤'? PŠr”¤,¥)cP;define.htm100644 5736 106 6362 6461114177 11713 0ustar attesoncbil Weight Matrix Definition

Weight Matrix Definition

A weight matrix for a pattern of length n is defined as a matrix of numbers W_i,x where i is in {1,2,...,n} and x is in {A,T,G,C} for dna.
The score of the string x₁...x_n is given by:

W_1,x₁ + W_2,x₂ + ... + W_{n,x_n}

For example, the weight matrix for a eukaryotic promotor cap region (Figure 25 of the 1992 edition of the text):

	-2		-1		0		1		2		3		4		5

A	-0.43		-5.01		1.34		-1.06		0.02		-0.12		-0.51		-0.41
C	-0.77		1.08		-5.33		-0.24		-0.08		0.13		-0.19		-0.07
G	0.43		-4.50		-4.50		0.95		-4.50		0.02		0.48		0.22
T	0.54		-5.07		-1.67		0.01		0.50		-0.10		0.23		0.24
Concensus	T		C		A		G		T		n		G		t
	G												t		g

Example	T		C		T		G		T		A		T		G
Score	0.54	+	1.08	+	-1.67	+	0.95	+	0.50	+	-0.12	+	0.23	+	0.22	=	1.73

design.htm100644 5736 106 17535 6461114177 11756 0ustar attesoncbil Weight Matrix Design

Weight Matrix Design

Given a several sequences corresponding to a site of interest, how does one go about creating a weight matrix?

Here, we can rely upon statistical theory and choose the weight matrix so that the score represents the log likelihood ratio and so represents a likelihood test. The procedure ends up to be the following:

Tabulate the number of occurences of each nucleotide at each position:

...	-3	-2	-1	1	2	3	4	5	6	...

...	C	G	G	G	T	A	A	G	T	...
...	A	A	G	G	T	A	T	G	C	...
...	C	A	G	G	T	G	A	G	G	...
...	T	G	G	G	T	A	A	C	T	...
...	C	A	A	G	T	A	A	G	C	...
...	A	A	G	G	T	A	G	G	C	...
...	A	T	G	G	T	G	A	G	T	...
...	T	T	G	G	T	A	A	G	G	...
...	A	A	G	G	T	A	T	T	T	...
...	A	A	G	G	T	A	A	G	G	...
										Total
A	5	6	1	0	0	8	7	0	0	27
C	3	0	0	0	0	0	0	1	3	7
G	0	2	9	10	0	2	1	8	3	35
T	2	2	0	0	10	0	2	1	4	21

Total	10	10	10	10	10	10	10	10	10
Consensus	A	A	G	G	T	A	A	G	B

Divide each entry (including the row sums) by the column sums:

-3 -2 -1 1 2 3 4 5 6
Nucleotide
Total
A 0.5 0.6 0.1 0.0 0.0 0.8 0.7 0.0 0.0 0.300
C 0.3 0.0 0.0 0.0 0.0 0.0 0.0 0.1 0.3 0.078
G 0.0 0.2 0.9 1.0 0.0 0.2 0.1 0.8 0.3 0.389
T 0.2 0.2 0.0 0.0 1.0 0.0 0.2 0.1 0.4 0.233
Divide each entry by the normalized row sums:

-3 -2 -1 1 2 3 4 5 6
Nucleotide

A 1.67 2.00 0.33 0.00 0.00 2.67 2.33 0.00 0.00
C 3.86 0.00 0.00 0.00 0.00 0.00 0.00 1.29 3.86
G 0.00 0.51 2.31 2.57 0.00 0.51 0.26 2.06 0.77
T 0.86 0.86 0.00 0.00 4.29 0.00 0.86 0.43 1.71

Finally, take the logarithm of each entry, handling zeros appropriately:

	-3	-2	-1	1	2	3	4	5	6
Nucleotide
A	0.51	0.69	-1.10	-10.00	-10.00	0.98	0.85	-10	-10
C	1.35	-10.00	-10.00	-10.00	-10.00	-10.00	-10.00	0.25	1.35
G	-10.00	-0.66	0.84	0.94	-10.00	0.66	-1.36	0.72	-0.26
T	-0.15	-0.15	-10.00	-10.00	1.46	-10.00	-0.15	-0.85	0.54

gene.htm100644 5736 106 2077 6461114177 11376 0ustar attesoncbil Gene Finding

Gene Finding

Prokaryotic genes are relatively easy to locate:
- Promoters are well characterized.
- Long open reading suggest the presence of genes.
However, for eukaryotes, it is more difficult:
- There are many types of transcription factor binding sites which work in conjunction with each other, most of which are not well characterized.
- Because of splicing, open reading frames are shorter and splice site (particularly acceptors) are difficult to locate.
Gene finding programs attempt to automatically find genes in unannotated sequence.

intro.htm100644 5736 106 2453 6461114177 11611 0ustar attesoncbil Pattern Matching Introduction

Pattern Matching Introduction

Instructor (me):

Kevin Atteson, 2-5581

atteson@peaplant.biology.yale.edu

Subject matter:

Pattern matching is the search for various patterns in long texts. Typical patterns might be:

Genes or signals related to genes:
- Transcription factor binding sites
- Cap sites
- Splice signals
- Start and stop codons
- Polyadenylation signals
Protein sequence motifs (e.g. PROSITE patterns).

We will discuss these systems from a computational perspective, that is, we will describe how pattern matching systems work.

naive.htm100644 5736 106 11521 6461114177 11574 0ustar attesoncbil The Naive Algorithm

The Naive Algorithm

The naive algorithm is to search every location of the string t for the pattern p.
As an example, consider searching for the pattern p = AAATA in the text t=AATAAAATA: A A A T A A A T A A A A T A A A A T A A A T A A A A T A A A A T A A A T A A A A T A A A A T A A A T A A A A T A A A A T A A A T A A A A T A A A A T A A A T A A A A T A A A A T A A A T A A A A T A A A A T A A A T A A A A T A A A A T A A A T A A A A T A A A A T A A A T A A A A T A A A A T A A A T A A A A T A A A A T A A A T A A A A T A A A A T A A A T A A A A T A A A A T A A A T A A A A T A A A A T A A A T A A A A T A A A A T A A A T A A A A T A
The naive algorithm requires around m (n-m) operations in the worst case where m is the length of p and n is the length of t.
Is there a better way?

A	A	A	T	A
A	A	T	A	A	A	A	T	A

A	A	A	T	A
A	A	T	A	A	A	A	T	A

	A	A	A	T	A
A	A	T	A	A	A	A	T	A

			A	A	A	T	A
A	A	T	A	A	A	A	T	A

			A	A	A	T	A
A	A	T	A	A	A	A	T	A

			A	A	A	T	A
A	A	T	A	A	A	A	T	A

				A	A	A	T	A
A	A	T	A	A	A	A	T	A

				A	A	A	T	A
A	A	T	A	A	A	A	T	A

				A	A	A	T	A
A	A	T	A	A	A	A	T	A

				A	A	A	T	A
A	A	T	A	A	A	A	T	A

				A	A	A	T	A
A	A	T	A	A	A	A	T	A

next.gif100644 5736 106 475 6460670652 11377 0ustar attesoncbilGIF89añp€ÿÿp€!þ# Imported from XPM image: next.xpm!ù,@çÜ63333ÆB! Ã0 A0 Ã0 Ã0 0 ƒÁ`0 ƒÁ`0 ƒA @ ƒÁ`0 ƒÁ`00000000000000000000000000000000000000000000 000000 0000000000000000000000000000`À€ ;nn.gif100644 5736 106 2707 6461071204 11041 0ustar attesoncbilGIF87aœ-ðÿÿÿ,œ-þ„©Ëí£œ´Ú‹³Þ¼û†âH–æ‰¦ê ¶î ÇòL×öçúÎ£Áè }AÀoˆ Ë¤s"d>§™¨‘ŠXÙ.£ÉõŠGcxŒž-ì¶û ËçôºýŽÏë÷ü¾ÿ(³x3HHtØ“¨¸ÃØˆ£fÉ"IY¨vic©9#YÖ S4ŠXºyZ3™z² Zâúª$K b{ë‘«ËÁÛ«ñ Œ!hÏö·bt‹{º+åÆí[àná.zß ®°BåÉE5g -“CU-MI¤N±PvT—&÷šÆïŠu'æ¨-ÇókŸüäe¯½ûŠc=¾¸ó¿{@s³½þÇé;žü?{Ï¿}ûòã¿½ý~óÿ>Úájå+ÍùÞÖ½ð'LuðÃE7 >ú¥¯y4 ÿ¸ ¸à50cù Úë4(@©áî‚›i\äø¼ÖU0[¼Y! Ë“?”I… \ÈªO[õ°á ih¹RX'¢¸. "Ba-¬*^ w( mÄyQt «Kh>ð\±3[´Š¿Æ0ŠqŒd,£Ïx)rPñUj¤FµˆE.Æñ‰Eì"åˆÇ'äñŽtœã7,¸ÇúËX” ßø16éŠkÄ•Cêð¤(dåWŒ@òŽZ¢š€$º$U2“ª£«-H¥}f¢-cy Á Sö‘”ˆ\ U˜(²Ï@©Œb7e»Vî¢—h,¦1‰Ìd*s™Ìl¦3Ÿi€;other.htm100644 5736 106 3013 6461114177 11570 0ustar attesoncbil Other Methods of String Matching

Other Methods of String Matching

To summarize:
- The naive algorithm requires around m (n-m) operations in the worst case.
- The Knuth-Morris-Pratt algorithm always requires around n+m steps.
Another algorithm, called the Boyer-Moore algorithm, can sometimes solve the problem in around m+n/m steps and solves it in around m+n steps in the worst case by using tricks such as the following:

Consider searching for p=AAATA in t=AATACAATA. Since C does not occur in p it is not possible for p to occur in t. Hence, if one looks at the right location, on need only look at one character of the text.
The Aho-Corasick algorithm can find any one from a list of pattern strings in around m+n steps where m is the sum of lengths of all pattern strings by constructing a failure function similar to the Knuth-Morris-Pratt algorithm.

overview.htm100644 5736 106 2313 6461114177 12317 0ustar attesoncbil Pattern Matching Overview

Overview

prev.gif100644 5736 106 475 6460670652 11375 0ustar attesoncbilGIF89añp€ÿÿp€!þ# Imported from XPM image: prev.xpm!ù,@çÜ63333Æ# „B Ã0 AÀ0 Ã0 Ã0 À0 ƒÁ`0 ƒÁ`0 ƒA ƒ €Á`0 ƒ`00000000000000000000000000000000000000000000 000 0000000000000000000000000000000`À€ ;prob.htm100644 5736 106 5133 6461114177 11416 0ustar attesoncbil String Probabilities

String Probabilities

How do you determine if a pattern found in a text is significant?
One method is to determine the probability of the pattern occuring if the text is random.
However, these probabilities are not always obvious.
Consider the probability of the patterns AA and AT in (uniform i.i.d.) strings over the alphabet A,T of various length:
- In strings of length 2, both AA and AT occur with probability 1/4:
  
  AA AT
  AA AA
  TA TA
  TT TT
  AT AT
- In strings of length 3, however, AA occurs with probability 3/8 and AT occurs with probability 4/8:
  
  AA AT
  AAA TAA AAA TAA
  ATA TTA ATA TTA
  ATT TTT ATT TTT
  AAT TAT AAT TAT
- In texts of length 4, however, AA occurs with probability 8/16 and AT occurs with probability 11/16.
  
  AA AT
  AAAA ATAA TAAA TTAA AAAA ATAA TAAA TTAA
  AATA ATTA TATA TTTA AATA ATTA TATA TTTA
  AATT ATTT TATT TTTT AATT ATTT TATT TTTT
  AAAT ATAT TAAT TTAT AAAT ATAT TAAT TTAT

sig.htm100644 5736 106 3125 6461114177 11235 0ustar attesoncbil Signals for Gene Finding
Signals for Gene Finding

There are many signals associated with genes, each of which suggests but does not prove the existence of a gene.

Gene finding programs put together evidence from these various types of signals to suggest possible locations of genes in large unannotated sequences.

Examples of signals which can be modeled with weight matrices (in order):

Transcription factor binding sites.

Cap site.

Start codon.

Splice sites.

Stop codon.

Polyadenylation site.

Another important source of information for gene finding is the frequency of various codons in coding and non-coding regions. For example:

The stop codons, TAA, TAG and TGA occur infrequently in coding regions.

Codon's appear with different frequencies depending upon their neighbors and the local secondary structure.

The frequencies of codons in coding and non-coding regions are accounted for in gene finding programs by using a log likelihood ratio similar to a weight matrix.

string.htm100644 5736 106 2635 6461114177 11766 0ustar attesoncbil String Searching
String Searching

The string searching problem is to find a string or pattern such as the polyadenylation concensus signal "AATAAA" in a body of text such as a gene.

String matching can be used to find:

Start and stop codons

Polyadenylation consensus signals

Consensus transcription factor binding sites (see the TRANSFAC database)

In our introduction to string matching, we will illustrate issues of algorithm design and analysis from the perspective of computer science and mathematics.

Those interested in further information are referred to the following book:

Dan Gusfield, Algorithms on Strings, Trees and Sequences, Cambridge University Press, 1997. This is a very readable book about algorithms in computational biology. Of particular interest to this lecture are Chapters 1 and 2.

toc.gif100644 5736 106 474 6460670652 11205 0ustar attesoncbilGIF89añp€ÿÿ!þ" Imported from XPM image: toc.xpm!ù,@çÜ6313Æc „BÃ0 Ã0‚ A0 Ã0 Ã0 €Á0 ƒÁ`0€@`0 ƒÁ` ƒÁ`0€@`0 ƒÁ`0€@`0000000000 0000000000 00000000 000000 0000 000000000 00000000000 00000000000000`À€ ;weight.htm100644 5736 106 1551 6461114177 11743 0ustar attesoncbil Weight Matrices
Weight Matrices

Some patterns are fuzzy and can't be defined efficiently and precisely as a set of strings. In particular:

Cap sites

Transcription factor binding sites

Splice sites

In such cases, weight matrices are used to define the patterns.

For information beyond what will be described here, see pages 23-42 of the 1992 edition of the text.

	-3	-2	-1	1	2	3	4	5	6
Nucleotide										Total
A	0.5	0.6	0.1	0.0	0.0	0.8	0.7	0.0	0.0	0.300
C	0.3	0.0	0.0	0.0	0.0	0.0	0.0	0.1	0.3	0.078
G	0.0	0.2	0.9	1.0	0.0	0.2	0.1	0.8	0.3	0.389
T	0.2	0.2	0.0	0.0	1.0	0.0	0.2	0.1	0.4	0.233

	-3	-2	-1	1	2	3	4	5	6
Nucleotide
A	1.67	2.00	0.33	0.00	0.00	2.67	2.33	0.00	0.00
C	3.86	0.00	0.00	0.00	0.00	0.00	0.00	1.29	3.86
G	0.00	0.51	2.31	2.57	0.00	0.51	0.26	2.06	0.77
T	0.86	0.86	0.00	0.00	4.29	0.00	0.86	0.43	1.71

AA				AT
AAAA	ATAA	TAAA	TTAA	AAAA	ATAA	TAAA	TTAA
AATA	ATTA	TATA	TTTA	AATA	ATTA	TATA	TTTA
AATT	ATTT	TATT	TTTT	AATT	ATTT	TATT	TTTT
AAAT	ATAT	TAAT	TTAT	AAAT	ATAT	TAAT	TTAT

AA		AT
AAA	TAA	AAA	TAA
ATA	TTA	ATA	TTA
ATT	TTT	ATT	TTT
AAT	TAT	AAT	TAT