Următorul conținut este furnizat de MIT OpenCourseWare sub o licență Creative Commons. Informații suplimentare despre licența noastră și MIT OpenCourseWare, în general, sunt disponibile la ocw.mit.edu. GEORGE CHURCH: OK, deci bine ai venit la a patra prelegere. Acesta va fi al doilea pe tema ADN-ului. Diferența majoră dintre această prelegere și ultima este că ultima, așa-numita ADN 1, ne-am concentrat pe tipuri de mutanți, secvențele lor de ADN strâns legate. Și acesta, vom vorbi despre cele mai îndepărtate secvențe de biopolimeri înrudite. Așa că am trecut prin modul în care puteți genera secvențe strâns înrudite și modul în care populațiile care sunt alcătuite din secvențe strâns legate obțin acele frecvențe alelelor prin deplasarea și selecția mutațiilor. Și am susținut că, în profunzime, la cel mai precis nivel, aveți o distribuție binomială în spatele fiecărui proces de derive a mutației și selecție, cel puțin sub un anumit set de ipoteze. Și apoi am trecut la o altă statistică foarte valoroasă, care este chi-pătratul, pe care o puteți utiliza într-o serie de scenarii diferite, dar, în special, cu studii de asociere, în care am făcut un caz simplu al unui sistem cu două alele cu două rezultate -- rezistența la HIV și sensibilitatea. Și apoi această asociere a condus la o discuție mai amplă despre alele și haplotipuri și genotipuri, în general, și despre cum se pot obține acelea și, în procesul de a face acest lucru, să se expună la erori sistematice aleatorii, o temă la care vom reveni. din cand in cand. Așa că astăzi, nu vom vorbi despre secvențe foarte strâns legate, ci despre secvențe foarte îndepărtate și care sunt algoritmii care sunt disponibili pentru găsirea acestora. Aceste secvențe înrudite la distanță obțin un set foarte diferit de căi. Aici, încercăm să căutăm indicii, ipoteze în, să zicem, noi secvențe de genom cu privire la ceea ce ar putea face noile gene. Deci vom începe prin a compara diferite tipuri de algoritmi care ne vor permite să facem aliniamente. În special, vom sublinia că eroul emisiunii de astăzi este programarea dinamică. Apare din nou și din nou pe tot parcursul cursului, nu doar în aliniere a secvenței în perechi, ci în alinierea multisecvențe. Și vom continua apoi la modul în care spațiul din computerul tău, sau memoria, dedicată procesării timpului determină compromisuri. Și, în unele cazuri, va trebui chiar să sacrifici acuratețea sau completitudinea. Și acest lucru duce, de asemenea, la problema găsirii genelor, un anumit tip de comparație de secvențe îndepărtate. Cei interesați sunt găsirea motivelor care sunt implicate în găsirea genelor. Și, în cele din urmă, vom încheia cu modelul Markov ascuns, cel mai simplu la care m-am putut gândi și care ar ilustra cu adevărat ideea de modele Markov, modele probabilistice și ascundere. Și astfel acest lucru este ilustrat cu o singură dinucleotidă cu două stări. Așadar, aceasta pune în context -- în primele două prelegeri, am vorbit despre arborele vieții și despre cum, chiar în esență, aveam formele comune și cele mai simple , care împărtășesc codul genetic simplu. Și asta a fost... și apoi ultima dată, am vorbit despre vârful unei ramuri a unuia dintre acești copaci-- practic, ramura umană a ramurii animalelor. Și ce s-a întâmplat la vârf în ultimele 5.000 de generații, de la blocajele destul de semnificative care au rezultat, care au precedat explozia populației. Și de această dată, vom vorbi despre întregul copac și despre modul în care aceste ramuri foarte adânci pot fi obținute prin compararea secvențelor de biopolimeri. Unii dintre cei mai timpurii arbori ai vieții s-au bazat pe secvența de ARN ribozomal, deoarece este ceva destul de ușor de urmărit până la strămoșii comuni. Dar, de asemenea, doriți să puteți face acest lucru cu o varietate de proteine, dintre care unele merg doar pe o distanță scurtă urmăribil în secvență, iar unele dintre ele merg înapoi. Ce putem face cu programarea dinamică? Am făcut aluzie la multiplele sale utilizări de-a lungul cursului. Iată câteva exemple. Am menționat deja asamblarea secvenței puștilor. Acest lucru este relativ ușor, deoarece secvențele sunt destul de strâns legate între ele. Aliniamentele multiple includ asamblarea secvenței, unde aveți mai multe secvențe similare. Dar, pe măsură ce ajungi la secvențe din ce în ce mai îndepărtate, poți culese din ce în ce mai multe despre concluzii structurale și funcționale despre proteine ​​și acizi nucleici atunci când ai un număr foarte mare , în sute. Și vom vedea provocările care apar acolo. Repetările sunt o particularitate - puteți avea repetări într- un genom sau putem avea aliniamente între diferite specii. Acum, cântecul păsărilor pare puțin deplasat aici. Dar din punct de vedere istoric, este una dintre primele aplicații ale programării dinamice în care, într-un fel, aveți o axă a timpului continuă și o eșantionați în puncte discrete, de multe ori, pentru a proba intensitatea înregistrării audio. Și aceasta va avea un analog mai direct decât alinierea secvenței, ceea ce vom face astăzi. Mai târziu, când facem analizele ARN, expresia genelor va arăta un algoritm direct de deformare a timpului , care este foarte asemănător ca linii cu cântecul păsărilor. Și apoi, în sfârșit, modelele Markov ascunse, care ar fi ultimul lucru astăzi, folosesc programarea dinamică ca parte a procesului prin care se iau deciziile cu privire la modelul care este reprezentat, modelul Markov ascuns. Și aceste modele Markov ascunse, la rândul lor, ne permit să facem căutări de gene ARN , predicție de structură, omologii ale proteinelor la distanță, recunoaștere a vorbirii și așa mai departe. Deci, există trei tipuri de alinieri și scoruri pe care le vom discuta pe diapozitivul numărul 5. Dihotomia principală este între global și local. Inițial, în alinierea secvenței în anii '70, Needleman-Wunsch avea un algoritm global, care a fost modificat - algoritmul local al lui Smith și Waterman - aproximativ un deceniu mai târziu. Și diferența majoră aici este că într-un algoritm global, aveți motive să credeți că secvențele se aliniază cap la cap. Și chiar vrei să întrebi câte nepotriviri, inserări și ștergeri există la mijlocul secvenței? Deci, de exemplu, este posibil să aveți două proteine ​​care au într-adevăr același loc de pornire și oprire. Sau s-ar putea să ai un cromozom întreg și pui întrebări despre haplotip, așa cum eram în ultima clasă, care ar fi, ce mutații sunt în cis pe un cromozom față de altul? Un alt exemplu este că s-ar putea să scanați un cromozom pentru un motiv care apare din nou și din nou, cum ar fi o repetiție Alu sau un motiv de legare a factorului de transcripție . Și aceasta poate fi la mijlocul unei secvențe, la sfârșitul alteia sau la mijlocul ambelor. Aici, este la capătul uneia și la mijlocul altuia. Și este scurt și local. Și astfel nu doriți să constrângeți capetele secvenței să se alinieze. Și nu doriți să penalizați dacă există o abatere de la alinierea capetelor. Făcând acest lucru cu un pas mai departe, astfel încât să nu fie în interiorul niciunuia, într- un ansamblu ideal -- ansamblu de secvență de pușcă, așa cum am vorbit data trecută -- v-ați aștepta, ca un singur fragment -- un fragment de clonă -- să se încheie, sperăm , aveți puțină suprapunere la începutul următoarei și veți putea sări de-a lungul acestor pietre de treaptă pentru a ajunge la sfârșitul secvenței. Pentru că nu poți ordona totul. Dar acest sufix ideal, unde un sufix al unuia se suprapune cu sufixul sau complementul de vers al altuia, acest tip de aliniere poate fi imperfect din cauza erorilor de la sfârșitul acestor secvențe. Deci, în general, vom vorbi despre global versus local. Și aceste secvențe specifice vom reveni la câteva diapozitive de acum. Acum, doriți să aveți un algoritm de notare. Vom folosi această măsurătoare de punctaj foarte simplă în mod repetat în timpul acestei discuții. Și aici, dăm doar plus 1 pentru fiecare potrivire perfectă, indicată de două puncte unde a se potrivește cu a și minus 1 pentru fiecare nepotrivire, indicată de x, unde c nu se potrivește cu a, de exemplu. Deci avem cinci potriviri perfecte și cinci nepotriviri în acest caz. Și deci este un total de 5 minus 3 este 2. Și în cazul local, nu vom cere ca capetele să se alinieze. Și să putem scăpa puțin, astfel încât acum să fie patru potriviri perfecte și să nu penalizăm nepotrivirile terminalelor. Și astfel avem un total de patru, care, dacă acestea ar fi scoruri direct comparabile, ar fi un scor superior. Și puteți vedea sufixele, aici, vă impuneți să fie la capete. Și este un scor de 3. Deci acum vom compara diferite moduri de căutare prin secvențe. Acum, acela a fost o potrivire exactă cu nepotriviri, unde nepotrivirile sunt penalizate. Și așa că o căutare exactă, o căutare cu adevărat exactă, este destul de rară - poate un site de restricții, ceva de genul ăsta. Puteți extinde aceasta la o expresie regulată în care inserările sunt restricționate. Ei, în acest caz, o inserție poate fi indicată de orice bază. A, C, G sau T pot apărea. Și apoi numărul pe care îl vei tolera este indicat printr-un interval numeric - de la zero la nouă, în acest caz. Și astfel exemplul particular dat - acest semn egal înseamnă doar că acesta este un exemplu. Deci C, G sunt stricte la capete. Și apoi s-a întâmplat să aibă două As acolo, care un A este un exemplu de nucleotidă care satisface abrevierea N. N este tot posibil. Dar ați putea, în mod similar, să aveți parantezele de la zero la nouă s-ar putea referi la o secvență scurtă, cum ar fi o secvență G și așa mai departe. Deci ai putea obține un număr cunoscut de repetări. Și asta ar putea reprezenta observația empirică că aveți de la zero la nouă repetări AG. Acum, în exemplul anterior, doar am penalizat ori de câte ori a fost o nepotrivire cu o sumă fixă. Dar ai putea avea o matrice de substituție, care ar codifica de fapt observațiile tale. Când vă uitați prin secvențe naturale și le aliniați, cât de des obțineți un A care înlocuiește un G? Și astfel penalizarea nu ar fi un minus strict 1. Ar fi ceva ce ai căuta într-un tabel. Și în acel tabel, diagonala ar fi potrivirile, iar cele în afara diagonalelor ar fi nepotriviri specifice. Și vom arăta cum obținem o astfel de matrice și cum o folosim. Acum, atunci puteți avea o matrice de profil. Sau acest PSI înseamnă sensibil la poziție. Și sensibilitatea la poziție înseamnă că aveți un tabel de căutare diferit pentru fiecare poziție din biopolimerul dvs. Și asta are sens pentru că nu toate pozițiile au același set de la fel - sau au același tip de substituții care sunt permise. Așadar, între paranteze de aici, acestea sunt nume reale de programe care sunt disponibile, fie în pachete comerciale, fie gratuit. BLAST este Secvența de aliniere locală de bază . Iar N se referă la nucleotidă. Și aici, PSI-BLAST, din nou, sensibil la poziție. Acestea sunt unele dintre cele cu care te vei întâlni cel mai des. Versiunile originale ale BLAST aveau ca scop principal să aibă cel mai mare bloc de secvență învecinată fără goluri. Și au existat așa-numitele statistici Carlin care ți-ar spune că aceasta este cea mai mare secvență care îți va oferi cea mai bună probabilitate. Dar apoi s-a recunoscut pe scară largă că atunci când oamenii evaluează de fapt potrivirile dintre două secvențe, ei nu evaluează doar cele mai lungi secvențe fără întreruperi. Ei sunt de fapt interesați de semnificația unei secvențe care poate include inserții și ștergeri. Și astfel BLAST a fost extins pentru a include goluri. Și înainte de această istorie lungă din anii '70 este Needleman-Wunsch și Smith-Waterman pe care le-am menționat, una globală și, respectiv, locală, care ar permite un număr mare de inserții și ștergeri de baze unice și de baze multiple, așa cum este determinat. de parametrii care au fost fie setați manual, fie determinați empiric. Și vom încerca să subliniem modalitățile prin care acest lucru poate fi determinat empiric. Și, în cele din urmă, modelele Markov ascunse au într-adevăr o abordare probabilistică pentru fiecare dintre acestea, permițând modele sensibile la poziție și care sunt extensibile nu doar acolo unde fiecare poziție are un set de probabilități, dar pot exista dependențe de pozițiile adiacente. Și vom ajunge la asta până la sfârșit. Și când am vorbit în prima clasă despre diferite definiții ale complexității, una dintre ele despre care am vorbit a fost complexitatea computațională, sau duritatea, a cantității de timp pe care o ia, sau cantitatea de spațiu, sau spațiu și timp, care este nevoie pentru a rezolva o problemă. Și aceasta este cu siguranță o ilustrare bună în discuția de astăzi despre programarea dinamică. Pentru că atunci când vrem să facem fie o aliniere a secvenței în perechi, fie o aliniere a mai multor secvențe - să începem cu perechi, aliniem k egal cu 2 secvențe de lungime n și permitem goluri. Acum, dacă le comparăm doar fără lacune, așa cum am făcut în slide-urile anterioare, este banal. Este liniar cu numărul total de baze. Este liniar în interior. Și asta, desigur, crește foarte grațios. Dar dacă ai un foarte naiv-- și voi stabili un om de paie aici-- ai un algoritm foarte naiv , atunci vei continua și vei pune un gol în orice poziție posibilă la partea de sus în combinație cu fiecare poziție posibilă în partea de jos. Și asta înseamnă că există n în partea de sus și n în partea de jos pentru un total de 2n poziții posibile pe care le-ai putea pune într-un decalaj. Și decalajul poate fi de orice lungime, așa cum vedeți în dreapta aici a diapozitivului 7 este că puteți avea un decalaj până la lungimea n. Deci aproximativ vorbind, un astfel de algoritm naiv ar scala foarte exponențial n la puterea 2n. Și acest lucru este enorm pentru n zeci. Și când n este în miliarde, atunci poți să uiți de asta. Nici măcar nu mai vorbim despre computere sau particule din univers. Și asta pentru k este egal cu 2, cel mai simplu caz posibil în care aliniați două secvențe. Dacă aliniați mai multe secvențe -- vom ajunge la asta într-un moment -- cu siguranță devine exponențial în k, chiar și în algoritmul a-non naiv. Deci vom arăta că va fi non-exponențială în n, lungimea secvențelor. Dar pentru a face asta, pentru a evalua algoritmii, îi putem face -- pe unii dintre ei le putem face teoretic. Și de fapt, pentru programarea dinamică, vom arăta că vă puteți convinge că un algoritm n pătrat este precis. Dar altele, va trebui să facem empiric. Și vreau doar să iau deoparte aici pentru a vorbi despre cum a fost făcută o anumită comparație a programelor de aliniere a secvenței. Deci, lucrul esențial, nu doar pentru acest test, ci și pentru mulți pe care îi veți vedea în acest curs și pe care poate doriți să-l faceți în propriile proiecte, doriți să lăsați deoparte un set de antrenament în care parcurgeți o serie de algoritmi. sau un număr de parametri din cadrul unui algoritm pentru a evalua care dintre ei sunt cei mai buni. Și odată ce ați determinat algoritmii care sunt cei mai buni sau parametrii care sunt cei mai buni, atunci doriți să aveți un set de testare care este independent. Asta înseamnă și neredundant. Deci, setul de antrenament, dacă utilizați setul de antrenament ca set de testare, vă puteți liniști într-un sentiment de complezență pentru că a fost supraantrenat. Și, practic, ești capabil doar să rezolvi problemele pe care le-ai pus înainte. Deci doriți un set de testare separat. Și asta s-a făcut în acest caz. Avem nevoie de un fel de criterii de evaluare. Așa că am vorbit despre scorurile pe care le-ați seta pentru a nota dacă o aliniere este mai bună decât o altă aliniere. Dar în plus, când vrei să compari doi algoritmi care îți pot da același scor, vrei să ai un criteriu de evaluare externă. În mod obișnuit, criteriul de evaluare pe care cineva l-ar putea avea este sensibilitatea și specificitatea. Ocazional, veți găsi în literatură unde oamenii se vor concentra doar pe unul sau altul. Dintr-un motiv sau altul, nu vor să rateze nimic. Așa că vor să-și păstreze falsul -- vor să-și reducă falsul pozitiv cât mai mult posibil. Sau nu vor să treacă prin munți de producție, așa că mențin falsele pozitive jos. Dar chiar vrei să le ai pe ambele foarte scăzute. Și uneori acest lucru este reformulat ca sensibilitate și specificitate, unde sensibilitatea este numărul de accesări adevărate pe care le-ați prezis față de numărul total de accesări adevărate. Acesta este, să zicem, în setul tău de antrenament, unde știi care sunt adevăratele lovituri dintr-o sursă externă. Și apoi specificitatea este numărul de accesări adevărate pe care le-ați prezis peste toate accesările pe care le-ați prezis, adevărate și false. Acum, acest adevăr aici care vine în setul tău de antrenament , de unde vine acesta? Dacă am avea acces la adevăr, în general, atunci pentru ce ne trebuie acești algoritmi? Și răspunsul este că avem acces , poate, la un adevăr superior sau la ceva care se află în afara alinierii secvenței. Și aceasta este cristalografie, genetică și biochimie. Din motivele pe care le vom aborda în partea de proteine ​​a acestui curs, cristalografia este capabilă să detecteze relații mult mai vechi între biopolimeri decât numai secvența. Genetica similară în biochimie poate testa ipotezele structurale și funcționale prin cheltuieli mari. Și deci acestea sunt scumpe. Și acesta este motivul pentru care sunt grozavi pentru a face seturi de antrenament, dar nu vor înlocui neapărat alinierea secvenței și scorurile. Așadar, aceasta a fost configurația pentru acest slide, adică Bill Pearson, care a dezvoltat algoritmul FASTA, printre altele, a făcut o evaluare amănunțită a diferiților algoritmi. FASTA era unul care se baza pe cuvinte, adică potrivirile exacte ale unor lungimi fixe pe care utilizatorul le putea seta; FASTP, care s-a bazat pe aceste blocuri de lungime maximă fără goluri în el. Blitz este o variație a algoritmului Smith-Waterman, adică o programare dinamică completă , despre care vom vorbi în scurt timp. Aceasta este o versiune extrem de paralelizată a acesteia, versiunea paralelă timpurie a acesteia. Deci diferiți algoritmi pentru realizarea alinierii au fost comparați, diferite matrice de substituție și diferite baze de date. Doar în cazul în care a existat o părtinire a bazei de date, el a inclus asta. Și așa vom vorbi despre matrice de substituție într- un moment. Dar, practic, acestea sunt aminoacizii sau nucleotidele - ce aminoacid, în acest caz, poate înlocui un alt aminoacid în segmentele de proteine ​​reale care au divergent cu aproximativ cantitatea pe care doriți să faceți testul. Și aceste numere diferite se referă doar la cât de îndepărtat sunt legate proteinele. Cu cât numărul este mai mare, cu atât acestea sunt mai îndepărtate înrudite în cazul matricelor PAM. Deci acum, de ce a făcut asta cu un nivel de proteine, mai degrabă decât la nivelul acidului nucleic? Ei bine, din punct de vedere istoric, este pentru că nu au existat secvențe de acid nucleic . Au fost în mare parte secvențe de proteine. Dar chiar și astăzi, există, evident, mult mai multă secvență de acid nucleic. Dar există un motiv real pentru a face asta la nivel de proteine, și anume că, atunci când te uiți la codul despre care am vorbit în aceste prelegeri, ceva de genul leucina poate fi reprezentat de șase codoni diferiți, care pot avea nucleotide extrem de diferite. secvente. Deci, de exemplu, CUG este valabil și UUA. Și aceștia au doar o singură nucleotidă din trei. Și pe perioade lungi de timp, dacă există o selecție puternică asupra proteinei și o selecție relativ slabă asupra acidului nucleic, sau chiar ar putea exista presiune asupra acidului nucleic pentru a se schimba din motive pe care le vom discuta în a doua jumătate a acestei prelegeri , acea presiune asupra secvenței de nucleotide poate face ca secvența de nucleotide să se schimbe mult și secvența de proteine ​​să nu se schimbe deloc. Deci, un exemplu de presiune este dacă ARNt-urile se schimbă în abundența lor, atunci ar exista o presiune ca utilizarea codonilor să se schimbe. Există câteva motive pentru a face acest lucru la nivel de nucleotide. De exemplu, dacă comparați secvențe care nu codifică proteine, acesta este un motiv evident. Dacă aveți multe inserții și deleții sau un fenomen biologic complicat, cum ar fi splicing-ul ARN, care face ca proteina să fie defazată - proteina dedusă să fie defazată sau greu de dedus - atunci ați face acest lucru la nucleotidă. nivelul secvenței. Acum, voi arăta acest diapozitiv de două ori. Prima dată, o să considerăm un dat că ni s-a dat această aliniere multisecvență și nu ne vom întreba acum cum am obținut-o. Dar vom folosi acea aliniere multisecventa pentru a deriva, sau pentru a vorbi despre cum am obtine, o matrice de substitutie. Și aici, o matrice de substituție, vă puteți gândi... aceasta este o aliniere multisecventă. Deci, în esență, avem o matrice de greutate, care, dacă aceasta ar fi sensibilă la poziție, am spune că în această poziție, C nu se schimbă niciodată. Dacă facem suficiente din aceste proteine și nu ne pasă de poziție, putem construi un set mare de matrice. Și, în general, vom descoperi că C tinde să înlocuiască C și foarte puține alte lucruri îl înlocuiesc. În cele din urmă, vei găsi și alte înlocuiri. Cisteina și triptofanul, C și W, sunt aminoacizi relativ rari și sunt foarte conservați. Altele pot fi înlocuite, după cum puteți vedea aici - treonina, serina și valina se pot înlocui unele cu altele. Deci acum să aruncăm o privire la modul în care se desfășoară acest lucru atunci când ne uităm la toate substituțiile posibile care pot apărea. Și asta este în diapozitivul 12. Dacă te uiți de-a lungul rândului de sus, sunt procentele, abundența aminoacizilor dintr-un anumit organism, să spunem E. coli. Și apoi există un cod cu o singură literă, de la A la Y. Și de-a lungul diagonalei este matricea de substituție, scorul care a fost determinat -- aceasta este matricea BLOSUM -- pentru un bloc reprezentat în blocuri înrudite la distanță. Aici, puteți vedea că diagonala reprezintă tendința aminoacidului de a se înlocui. Și acei aminoacizi, care, în general, nu sunt ușor de înlocuit - după cum am spus, sunt foarte conservați, ceea ce am subliniat în diapozitivul precedent - au fost cisteina, C și triptofanul, W. Și, de exemplu, W este cel mai puternic conservat. Este 22 de-a lungul diagonalei. Și consecința este că vor exista relativ puține valori pozitive în afara diagonalei. Și de fapt, pentru triptofan, nu există valori pozitive. Numerele de aici au fost generate în așa fel încât negativele vor tinde să anuleze pozitivele în aliniamente, aliniamente cunoscute, ale secvențelor care sunt la distanța evolutivă corectă unele de altele. Vrei să alegi... vrei să-ți faci matricea, dacă încerci să cauți proteine ​​înrudite foarte îndepărtate, vrei ca substituțiile pe care le eșantionezi în setul tău de antrenament să fie cât mai departe la aceeași distanță... - adică foarte îndepărtat înrudit. Și aceasta este una dintre greșelile care a fost făcută în matricea PAM timpurie . Au fost două greșeli, de fapt -- matematica -- ei bine, în primul rând, proteinele care au fost comparate erau foarte strâns legate. Pentru că proteinele strâns legate erau mai demne de încredere. Ai putea alinia secvențele închise mai ușor. Algoritmii nu trebuiau să fie sofisticați. Și copacii ar putea fi mai precisi. Dar apoi, pentru că făcuseră... deci a fost deja o părtinire, deoarece substituțiile pe care le obțineți în secvențe strâns legate nu sunt chiar aceleași. Și apoi se aplică unei metode de extrapolare matematică , care nu a fost adecvată în ceea ce privește evoluția reală și, de asemenea, nici măcar nu era corectă, matematic, deși aceasta a persistat timp de decenii ca cea mai comună - și încă - cea mai frecvent utilizată matrice. . Oricum, puteți vedea că, deși triptofanul nu are nicio diagonală pozitivă, ceva de genul arginină, aici, în acest albastru, are un 4 pozitiv off-diagonal și un pozitiv 10 pe diagonală. Deci, după cum ați putea ghici, care este cel mai probabil înlocuit cu arginina încărcată pozitiv? Este lizină încărcată pozitiv în condiții fiziologice. Și de aceea este în afara diagonalei. Și mai sunt și altele. Le-am codificat pe culori la fel ca și codul genetic, unde aminoacizii încărcați negativ se pot înlocui unul pe altul. Deci, semnificația acelui rând de sus, a abundenței procentuale, este că, dacă găsești două As care se potrivesc, asta nu este atât de semnificativ, deoarece acesta este cel mai frecvent aminoacid din acest organism. Pe de altă parte, dacă găsiți două C care se potrivesc, este foarte semnificativ. Pentru că acestea sunt rare. Și găsirea a două dintre ele în același loc într-o anumită aliniere înseamnă că este semnificativ. Deci atât abundența, cât și matricea de substituție pot fi utile. Deci, acum, vom trece printr-un punctaj real al unor aliniamente. Și dorim să facem acest lucru în această situație mai dificilă în care permiteți inserări și ștergeri. Deci, mai întâi, vom face, deși am spus cum se face că obținem potrivirea față de numerele nepotrivite ca o matrice de substituție completă , aici, vă puteți imagina că matricea de substituție are plus 1 de-a lungul diagonalei sale și minus 1 în afara diagonalei. astfel încât să puteți face toate calculele pe care vi le voi arăta în următoarele câteva diapozitive din capul vostru. Dar, de asemenea, imaginați-vă simultan că ar putea avea bogăția matricei de substituție pe care tocmai o aveam. Vom face asta, următoarele câteva, cu acid nucleic. Dar imaginați-vă că ați putea face acest lucru și cu aminoacizi. Matricea de substituție a acidului nucleic va fi 4 cu 4. Cea pe care tocmai am văzut-o a fost 20 cu 20 pentru aminoacizi. Indels, îi vom penaliza cu minus 2. Dar acesta este un număr arbitrar. Și vei vedea cât de critic este într-o clipă. Dar vă puteți imagina că acest lucru ar putea fi determinat empiric, la fel cum matricea de substituție a fost determinată empiric în diapozitivul precedent. Scorul de aliniere, atunci, va fi definit ca o sumă de coloane. Vom presupune că pozițiile adiacente sunt independente unele de altele. Și le vom nota independent și apoi vom lua doar suma. Aceasta ne oferă scorul de aliniere pentru o anumită aliniere, un anumit set de indels și un anumit set de offset de la o secvență la alta. Dar ceea ce vrem cu adevărat să facem este să trecem prin toate acele aliniamente posibile pentru a obține alinierea optimă, care este scorul maxim definit aici. Pentru a obține alinierea optimă, am dori să facem asta într-un timp mai puțin decât exponențial, cu cel puțin mai puțin decât exponențial pe n lungime a secvențelor. Deci vom folosi această pereche de secvențe, ATGA, ACTA, de două ori pe acest slide. Și o vom folosi în diapozitivele ulterioare, unde o vom face într-un mod ușor diferit. Și vom folosi acea măsură de scor foarte simplă - plus 1 din acea potrivire perfectă, minus 1 pentru nepotrivire, minus 2 pentru indel. Și ceea ce obținem aici este că acestea sunt doar două dintre multele aliniamente diferite pe care le-am putea avea cu inserții diferite aici. În stânga, numărul unu, cel mai extrem caz, fără inserții sau ștergeri în nicio secvență. Numărăm doar nepotrivirile. Sunt două meciuri, două nepotriviri. Și deci sunt doi plus 1, doi minus 1. Și se anulează. Iar scorul este 0 pentru cel din stânga. Apoi, cel din dreapta, am trecut la... a permis o inserție pe fiecare șuviță, indicată printr-o liniuță în secvența opusă. Și acum, vezi că ai trei potriviri perfecte, ceea ce înseamnă o creștere a numărului de potriviri perfecte, dar penalizate cu două indeluri, care sunt ambele negative 2. Deci este plus 2 minus 2 minus 2 pentru minus 1. Deci nu este o îmbunătățire pentru alinierea din stânga dacă acceptăm valorile de scor pe care le-am avut în diapozitivul anterior - plus 1, minus 1 și minus 2 pentru indels. Dacă, în schimb, spunem, ei bine, indel-urile chiar nu ar trebui penalizate atât de mult -- putem accepta inserări și ștergeri în astfel de secvențe, vom penaliza cu minus 1, o vom penaliza la fel ca o nepotrivire -- acum scorul este 3-- scor pentru cel din dreapta, cu trei potriviri perfecte și două inserții-ștergeri, este acum plus 1. Și le bate pe cele perfect aliniate. Deci, dacă 1 este mai bun decât 2 depinde de scorul indel pe care l-ați ales. STUDENT: Pot să vă pun o întrebare? GEORGE CHURCH: Da, întrebare. STUDENT: Acum că aliniați două secvențe diferite și, în cazul indelului, permiteți inserții peste tot -- Adică, teoretic ați putea avea milioane de acestea. Dar, în realitate, acest [INAUDIBIL] secvențele în majoritatea cazurilor ar fi nu. Ai ști ce este. Nu poți... GEORGE CHURCH: Știm ambele secvențe. Acestea sunt secvențe pe care le comparăm două organisme diferite. STUDENT: Corect. Deci, dacă le cunoașteți pe amândouă , atunci ce rost are să permiteți toate aceste indel [INAUDIBILE].. GEORGE CHURCH: Deci întrebarea este, de ce permitem inserări și ștergeri? Și motivul este că în timpul evoluției, să zicem, fie evoluție de laborator, fie antică, inserțiile și ștergerile sunt mutații valide. Și așa că încercăm să determinăm locurile cele mai probabile în care inserările și ștergerile ar fi putut avea loc pe parcursul divergenței a două secvențe. Și credeți-mă, inserările și ștergerile sunt foarte, foarte frecvente. Deci, de aceea le permitem. Acum, de ce inserarea-ștergerile ar putea fi foarte penalizate sau puțin penalizate ar putea depinde de o poziție din secvență. Deci, de exemplu, dacă aveți un factor de transcripție în care geometria lui precisă este importantă sau o helix alfa și o proteină sau traducerea unui cod genetic în care o inserție va arunca din greșeală întregul cadru, așa cum am avut în receptorul de chemokine în ultima clasă, atunci vrei să penalizezi un indel foarte puternic. Pe de altă parte, dacă aveți o grămadă de motive care sunt oarecum separate prin linkere variabile, atunci inserarea-ștergerea ar putea fi aproape zero, fără penalizare. Deci, puteți vedea că contează și că ar putea fi sensibil la poziție. S- ar putea să nu fie o mărime pentru toate. Dar acestea sunt determinate empiric - pot fi determinate empiric. Deci iată eroul... programarea dinamică. Sperăm că am motivat că putem marca. Putem determina matrice de substituție și indel utile din punct de vedere empiric. Acum, cum le aplicăm? Și programarea dinamică se extinde dincolo de biologie, așa cum am făcut aluzie. Și un astfel de algoritm rezolvă fiecare subproblemă o singură dată și își salvează răspunsul într- un tabel, evitând astfel munca de recalculare a răspunsului de fiecare dată. Deci omul de paie pe care l-am vomitat înainte de a avea această problemă exponențială este foarte ușor de rezolvat. Și felul în care se rezolvă este că acesta este modul subproblema de a face față. Și ideea de recursivitate, pe care am atins-o ușor când am definit factorialul, n factorial ca fiind egal cu n ori n minus 1 factorial, definindu-l deci în termenii ei înșiși. Dar lucrul cheie din spatele acestei definiții și a celor pe care le vom avea aici este că, atunci când definiți ceva în sine, ar fi bine ca apelul să fie o problemă mai simplă și, în cele din urmă, să terminați. Și asta este ceea ce avem aici. Voi da două exemple în diapozitivul 17 și în diapozitivul următor, unul global și unul local. Aceasta se va face în termeni de comparație cu tetranucleotide, aceeași cu care ne-am confruntat tot timpul. Iar celălalt va fi într-o secvență mai abstractă. Aici, modul în care se face sub-subproblema prin recursivitate este să spunem că definim scorul de aliniere a acestor două tetranucleotide ca maxim de-- și apoi există trei opțiuni. Poate fi fie scorul de a avea o inserție pe șuvița de sus și aceasta este opțiunea de top. Cel din mijloc nu are inserții sau ștergeri pe niciuna dintre componente și doar evaluează ultima comparație de bază, care, în acest caz, este un A versus un A. Acum, așa se termină algoritmul. Când aveți o comparație cu o singură bază sau o singură bază în comparație cu o indel, atunci căutați algoritmul de notare sau valorile de scor pe care le-am folosit tot timpul. Deci, aici, să ne uităm la ultima coloană din dreapta. Scorul pentru un indel versus un A ar fi acel minus 2 pe care l-am presupus de-a lungul. Iar scorul unui A versus A ar fi diagonala matricei de substituție, care ar fi un plus 1 și apoi, aici, un minus 2. Și astfel puteți vedea că apelați aceste trei posibilități -- indel, fără inserare în partea de sus, fără inserare în partea de jos. Și iei maximum dintre acestea, oricare dintre acestea dă cel mai bun punctaj. Acum, asta necesită să te întorci și să apelezi din nou. Dar îl numești cu un simplu... ceri unul mai simplu. Deci, acum, veți lua maximul de ATG versus ACT. Și asta vă va cere să căutați maximul de AT AC. Și, în cele din urmă, va obține maximul de A versus A. Și apoi terminați. STUDENT: Scuză-mă. GEORGE CHURCH: Da. STUDENT: Presupuneți că partea de inserție este întotdeauna un 1? Partea de inserare este întotdeauna 1, nu? GEORGE CHURCH: Nu. Acest algoritm permite orice număr de inserții până la lungimea unei secvențe. Și veți vedea când vom face acest lucru în formă tabelară, cum fiecare posibilitate. Dar faci pe rând. Sunt doar trei cazuri aici. Tratându-vă cu doar trei cazuri la un moment dat, ajungeți să aveți de fapt întreaga generalitate a oricărui număr de inserări și ștergeri. Și asta este frumusețea acestui algoritm. Nu trebuie să faceți în mod explicit fiecare inserare posibilă cu fiecare ștergere posibilă. Trebuie doar să le treci o dată. BINE. Acum, am spus că voi face două tratamente cu anumite asemănări. Acestea sunt ambele programare dinamică a secvențelor în perechi. Cel precedent a fost global. Acesta este local. Singura diferență acum este că limităm scorul să fie mai mare decât 0. Nu permitem negativ. Deci asta înseamnă că nu penalizăm nepotrivirile, de exemplu, la capete. Amintește-ți când ți-am arătat acel exemplu specific de la început. Deci acum avem patru opțiuni - aceleași trei ca înainte plus 0. Și celălalt lucru pe care l-am făcut puțin diferit aici este, mai degrabă decât să avem o secvență specifică - acea tetra nucleotidă - aici, avem o secvență generală în care arăți că elipsele, secvența este până la i lung și până la j lung aici. Și în această etapă a punctajului, fie vei tăia elementul de secvență i și j -- aceasta ar fi o singură bază și faci acel scor în scorul central aici -- fie ai o inserție la de sus sau inserție în partea de jos. Deci aceasta este doar o reformulare a celei precedente, generalizată și transformată într-o aliniere locală, ceea ce, în general, este ceea ce fac oamenii. Oamenii fac mai degrabă aliniamente locale decât globale. Pentru că nu este sigur să spui că capetele secvenței tale se vor alinia. Dar le vom analiza pe ambele ca exemple. Acum, vom calcula acest lucru ca un algoritm rând cu rând. Acum, întâmplător, ai putea să oprești acest cadru de-a lungul marginii. Dar pentru a face ca algoritmul să fie același pentru început și pentru toți pașii intermediari, ceea ce faceți este să completați acest lucru cu numere astfel încât marginile să fie un număr foarte, foarte mic, care este mai mic decât suma tuturor scoruri pe care le-ai putea scoate din acest tabel, astfel încât să nu poți intra cu adevărat din acele margini. Trebuie să veniți din punctul zero, care este alinierea globală care necesită ca capetele să se alinieze. Deci, acest lucru necesită alinierea capătului din stânga. Și atunci prima comparație-- singura comparație pe care o poți face cu adevărat-- este A, A. Aceasta este comparația terminală. Și se întâmplă să fie o potrivire perfectă, așa că obține un scor de plus 1. Acum, următorul pătrat pe care îl puteți face este minus 1. Și amintiți-vă, fiecare dintre acestea are trei posibilități în alinierea globală. Amintiți-vă, poate fi o inserare, o ștergere sau doar o comparație directă a potrivirii cu nepotrivirea. Deci primul, inserarea și ștergerea au fost excluse. Nu aveau de gând să câștige scorul maxim. Deci practic ai primit 1. Devine puțin mai interesant când adaugi următorul C. Pentru a adăuga acest C pe axa orizontală fără a adăuga nimic pe axa verticală, asta înseamnă că ai un indel. Și asta înseamnă că ai meciul tău A-A. Dar acum, pentru a adăuga acest C, aveți un 2 negativ - o penalizare de minus 2. Și astfel, pentru rezultatul net este un minus 1. Și apoi, pentru fiecare următor, se presupune că extensia este aceeași ca indel inițial, care este tot negativ 2. Și deci aceasta este o potrivire A-A urmată de o inserție, două inserții sau trei inserții. Și trei inserții, desigur, care îți dau minus 5. Și continui să mergi prin asta. Fiecare dintre aceste pătrate, în esență, reprezintă maximum trei posibilități. Diagonala, dacă urmați linia diagonală galbenă de la 1 la 0, înseamnă că ați luat o potrivire A-A și o nepotrivire C-T, iar 1 negativ este anulat la 1 pozitiv și obțineți un 0. Alternativ , că 0 este de fapt maximul acelui scor individual în comparație cu un indel de la minus 1 plus această nepotrivire, care nu va fi mai bună decât 0, și un minus 1 plus nepotrivirea care vine pe orizontală, care, de asemenea, nu va fi mai bun decât 0. Deci ajungi cu 0, care este potrivirea perfectă plus o nepotrivire, fără indel. Și, în mod similar, puteți umple întregul tabel în acest fel. În sfârșit, acum, puteți urmări care sunt cele mai bune scoruri de la un capăt la altul aici, mergând până la meciul dvs. cu terminalul A-A din capătul din stânga până la meciul cu terminalul A-A din capătul din dreapta. Și puteți vedea că cel mai bun traseu de urmărire trece prin diagonală aici. Acest 0 este maximul dintre trei posibilități -- stânga-dreapta, sus-jos și diagonală. În mod similar, acest minus 1 a fost cea mai bună dintre cele trei posibilități. Amintiți-vă, aceasta este o aliniere globală care permite valori negative. Și maximul său a fost de-a lungul diagonalei și așa mai departe. Acesta este un exemplu al celor doi pași de bază. Tu ai configurat valorile de punctaj. Setați această matrice n de n sau n de m. Și apoi îl umpleți. Și asta este o operație n pătrat. Doar crește odată cu numărul... lungimea celor două secvențe. STUDENT: [INAUDIBIL]. GEORGE CHURCH: Întrebare. STUDENT: O diagonală nu este singura optimă... GEORGE CHURCH: Nu este. Este adevărat. STUDENT: [INAUDIBIL] GEORGE CHURCH: Așa este. Dacă aveți o diagonală care este echivalentă, atunci aceasta este o altă aliniere de secvență validă. Și, de fapt, apare destul de frecvent, atât în alinierea globală, cât și locală. Și apoi colțul din dreapta jos al diapozitivului 20 arată interpretarea specifică a acestui [? Brown?] set de erori, urmărirea particulară pe care am ales să-l evidențiem aici, care nu este singura. Și asta este interpretat în același mod în care am interpretat-- simbolic într- un diapozitiv anterior. Acum, acesta este, de asemenea, dintr- un diapozitiv mult mai devreme. Acesta este cel în care am avut motivul pentru a ilustra alinierea locală. Și pe partea stângă matricea este pentru alinierea locală folosind un algoritm Smith și Waterman. Și în partea dreaptă este alinierea globală folosind algoritmul de tip Needleman-Wunsch , pe care tocmai l-am folosit pe o secvență mai scurtă. Și aici, am subliniat diagonala, care dă un scor de 2 și are un traseu de-a lungul diagonalei magenta și ar avea interpretarea secvenței de sus direct peste secvența de jos. Pe de altă parte, dacă căutăm aliniamente locale și nu penalizăm offset-urile sau indelurile, atunci poți obține un exemplu. Și iată o altă urmărire magenta unde am mers-- potrivirea A-A nu este pe diagonală pentru alinierea secvenței globale, dar nu a fost penalizată. Deci preia 0-urile din celulele limită ale cadrului și doar preia potrivirea perfectă pozitivă 1. Și apoi, când adaugi un C, ia un altul, iar un alt C, altul a. Și toate cele patru se adună până la 4. Adăugarea unei baze suplimentare, totuși, nu ajută. Pentru că trebuie să fie o nepotrivire sau o inserare sau ștergere. Deci, trecerea de la 4 la un indel face ca acesta să scadă cu minus 2, dând cele două 2. Și mersul pe diagonală ridică o nepotrivire, care este o penalizare de minus 1. Deci nu poți face mai bine. Și asta determină marginile alinierii dvs. locale. Deci nu aveți doar un scor și o urmărire, dar aveți și puncte finale. STUDENT: [INAUDIBIL]. GEORGE CHURCH: Da, întrebare? Tu, da. STUDENT: Acum, când va începe, totuși, nu tocmai pe diagonală, ci în diagonală [INAUDIBIL]---- GEORGE CHURCH: Da, vei primi un mai lung... STUDENT: B, care evident nu este la fel de bun... - GEORGE CHURCH: Și apoi 4. STUDENT: Și apoi continui, te întorci la 4. GEORGE CHURCH: Și acesta este un alt exemplu, la fel ca și precedentul. Aceasta este o altă aliniere validă. Este încă o aliniere locală. Nu are punctele finale globale totale. Și are un scor egal cu motivul mai scurt. STUDENT: Deci cum se compară acestea două? Adică, vrei... GEORGE CHURCH: Sunt egali. STUDENT: --spunem pentru că celălalt este mai lung [INAUDIBIL] GEORGE CHURCH: Ei bine, în acest caz, algoritmul de notare a fost configurat în așa fel încât lungimea să nu fie luată în considerare, în afară de faptul că secvențele mai lungi au mai multe șanse de a avea mai multe meciuri perfecte. Deci, în acest caz, ar fi echivalente. Pe măsură ce ajungeți la matrice de substituție mai detaliate, șansele de a obține două scoruri identice sunt mai slabe. Dar cu acizii nucleici cu acest tip de punctaj simplu, apare tot timpul. Deci e bine. Ne-am negociat acum drumul de la un mod oribil potențial exponențial de a face aliniamente la ceva care se scalează de n ori m, unde acestea sunt lungimile celor două secvențe. Te-ai putea gândi la asta ca la o matrice dreptunghiulară, cum ar fi cele pe care le-am făcut. Și atât timpul, cât și cerințele de spațiu sau memorie pentru algoritm se vor scala prin această relație pătratică. Iar timpul în memorie este modest. Deci, în termeni absoluti, ar fi de ordinul unei comparații -- aceasta este comparația maximă -- trei pași de multiplicare și în calcularea intrării. Și memoria ar putea fi de ordinul unui octet. Structura datelor poate fi întreagă sau poate fi virgulă mobilă. Și din nou, trebuie să aveți o modalitate de a găsi intrările în tabel. Deci e bine. Se scalează grațios. Dar cât de mare este? Să presupunem că avem două genomi megabaze. Pentru a găsi intrări de această dimensiune, ar putea dori să lăsați deoparte 4 octeți. Și astfel aveți cei 4 octeți ori 10 până la al șaselea pătrat. Sau acesta este doar un joc de fotbal. Există diferite moduri în care ai putea strânge puțin acest lucru. Dar aceasta este 4 gigaocteți de memorie. Și pentru un procesor gigahertz, s-ar putea să puteți face un milion de intrări pe secundă, astfel încât, cu 10 până la 6 intrări pătrate, înseamnă aproximativ 10 zile. Acum, acesta este un genom destul de mic. Majoritatea genomurilor sunt mai mari de 1 megabază. Și atunci când am avut discuțiile la începutul Proiectului Genome, unul dintre lucrurile pe care oamenii le-au adus în discuție a fost cum vom compara un miliard de perechi de baze cu un miliard de perechi de baze dacă scopul acestui proiect este de a face genomul uman de trei miliarde de perechi de baze? Și, desigur, pe atunci, majoritatea computerelor aveau 4 gigaocteți, iar un gigahertz era un computer destul de remarcabil. Și, desigur, răspunsul a fost că nu aveam de gând să facem o programare dinamică completă a genomului uman împotriva lui însuși. Aveam de gând să trișăm în diferite moduri. Și a fost nevoie de recunoașterea faptului că era într-adevăr practic și, din punct de vedere biologic, nu prea o scurtătură pentru a căuta mici puncte de ancorare care să îți spună că poate secvențele nu se aliniază cap la cap, dar există un punct de ancorare în care ai suficient. baze sau suficienți aminoacizi la rând pe care să îi poți spune, OK, iată un punct în care se aliniază cu siguranță. Să facem acum presupuneri rezonabile după câte indeluri pot exista, de exemplu, știind cât de diferite sunt cele două secvențe. Și, așadar, dacă cunoașteți diferențele de secvențe, atunci puteți spune, nu voi permite mai mult decât un număr rezonabil de indels bazat pe cât de diferite sunt secvențele. Și faci o bandă care are o lățime îngustă - iată un exemplu destul de extrem în care avem o lățime de 3. Și așadar, în loc să facem o matrice n pătrat complet în care ai umplut întregul lucru, facem doar această bandă, care este de ordinul lățimii benzii înmulțit cu lungimea celei mai lungi secvențe. Acum, acest lucru nu pare foarte impresionant pentru acest caz, deoarece n este mic, iar w este relativ mare. Dar dacă n ar fi miliarde și w ar fi, să zicem, de la 3 la 5, atunci ar fi o economie foarte semnificativă. Deci sunt două lucruri cheie aici. Unul este bandajul, iar celălalt obține punctele de ancorare. Deci, rezumatul pentru această jumătate a discuției este că programarea dinamică este într-adevăr modalitatea riguroasă de a compara două secvențe. Și după pauză, vom vedea cum puteți compara mai multe secvențe. Trebuie să lucrăm pentru o interpretare statistică a acestor aliniamente. Asta va necesita niște seturi de testare-- îmi pare rău, niște seturi de antrenament-- unde puteți vedea cum se comportă de fapt pe populațiile biologice reale de aliniamente de secvențe . Trebuie să calculăm fie o aliniere globală, fie una locală. Și ați văzut algoritmi pentru a face fiecare dintre aceștia și cum există diferențe importante, dar subtile între ei. Și am vorbit despre modalități prin care putem îmbunătăți enorm algoritmul utilizând funcțiile simple de notare sau cele complicate care sunt determinate empiric. Deci hai să luăm o mică pauză. Și vom reveni și vom vorbi despre alinierea multisecvență.