Ho delle query sequence da cui voglio iniziare a indagare. Questa sarebbe una inferenze elettronica che andrebbe poi andata a conermare i laboratorio. Questa è sicuramente predetta sulla scorta dell’algoritmo. Se non uso un ordinamento esatto mi serve un sistema per andare a vlautare la confidenza della soluzione che ho ottenuto.
[23-05-2023]
Metodi euristici perché sono algoritmi che non ci danno la soluzione esatta del problema, ma danno una soluzione approssimata al problema. Questi approcci risolvono il problema in maniera approssimata e in principio potremmo andare a perdere qualche soluzione e non trovare una qualche sequenza perché l’algoritmo se l’è persa. Alla fine dobbiamo avere un momento in cui dobbiamo valutare la significatività della soluzione proposta. Nulla vieta per usare un metodo di questo tipo per abbassare un termini del calcolo ordine, come dimensione della banca dati. I due metodi più famosi e sono FASTA e BLAST. FASTA è anche un formato in cui scrivo le sequenze nucleotidiche o aminoacidiche. Formato messo a punto per are le sequenze in input a quell’algoritmo.
Come metodo praticamente prima cerca dei match esatti in blocchi molto piccoli e poi cerca di estendere il tutto. Tutte le sequenze in cui non trovo un seed mi fanno abbassare il numero della banca dati. Type 1 e type 2 error: perdere una soluzione e metterne una di troppo. L’idea è cercare match esatti in porzione molto piccole. In questa maniera si abbassa la dimensione della banca dati.
Mi aspetto contengano un sacco di segmenti con match o sostituzioni senza troppe problematiche.
L’idea è confrontare le sequenze con questi frammenti (word) per cercare parole che siano in comune. Una porla è un a sotto stringa di lunghezza 34
Organizzo le parole e mi salvo la posizione di dove le parole compaiono. Alcune parole possono comparire più e più volte. Creiamo praticamente una sequenza, un k = 2 (come sotto sequenza da prendere in considerazione), scansioniamo la sequenza e prendiamo ciascuna parola (sottostringa grande k), mi segno pa posizione in cui la trova.
A questo punto sarebbe interessante andare a fare una indicizzazione di tutta quanta la banca dati. Questo è decisamente più comodo piuttosto che andarci a portare dietro tutta quanta la banca dati.
Cerco di trovare il numero di parola comuni e poi vedo anche il loro posizionamento. Il punteggio è la somma delle occorrenze comuni praticamente. Qui non sto facendo nulla di complesso è indicizzazione pura. Noi dobbiamo cercare di indicizzare ogni singola subject di una banca dati e posso farla una sola volta per tutte e pre ogni parola della query che incontro nella tabelle della banca dati mi calcolo il numero complessivo di occorrenze. A quel punto abbiamo sia quante volte abbiamo quella parola che le posizioni. Sappiamo quante volte e dove, una rispetto all’altra. Questi ci danno l’idea di avere anche il numero di spostamenti per andare ad avere parole identiche. Abbiamo tutte le posizioni, le occorrenze e gli spostamenti. Questi sono rappresentabili in una matrice dot plot, perché quelle parole identiche se le visualizzassi in una matrice dot plot rappresenterei delle piccole diagonali praticamente lunghe K. Le diagonali saranno più o meno sfaldate. La formazione di queste tabelle quando le vado a graficare mi indicano anche piccole regioni di allineamento perché sono dei seed questi, ma se non ci fossero nemmeno non avere nemmeno una similarità minima tra I e J e non avrebbe manco senso andarla a considerare. La complessità di fare tutto questo è lineare. Le tabelle possono essere lunghe al massimo $4^k$, in questo caso $4^2$.
Questo tipo di indicizzazione è comune sia a BLAST che FASTA. Siamo arrivati ad avere identificato delle micro regioni di similarità assoluta, siamo in match puro, di identità assoluta, in due sequenze di cui una viene da una qualunque della banca dati. So dove stanno, quante sono e posso usare quest informazioni rispetto alle regioni di identità, sulla scorta di quante sono per eliminare chi non ha un numero sufficientemente elevato e altro per capire che se sono vicinie a sufficienza potrebbero essere unite tra di loro in una qualche maniera.
FASTA e BLAST differiscono poi nella fase di extends dei seed praticamente.
Primo introdotto e usa come strategia, dopo aver indicizzato query e banca dati, per identificare le seq più simili una estensione che è basata sull’idea che graficamente viene visualizzati sulle dot plot. Visualizzo le diagonali, vedo che distanze abbiamo e le dimensioni dei pezzi non identici per unire pezzettini identici e ci faccio dei calcoli sopra per capire che sequenze vale la pena considerare per fare un allineamento esatto. E’ un procedimento che ha della fasi praticamente: