[a.a. 24/25] I.Gaita
Il rapido sviluppo delle tecnologie di sequenziamento del DNA, in particolare il Next Generation Sequencing (NGS), ha reso fondamentale il pattern matching delle letture brevi (short read) su un genoma di riferimento per estrarre informazioni biologiche significative.
Questo progetto presenta un’analisi approfondita di un algoritmo chiave proposto nella letteratura scientifica, incentrato sull’ottimizzazione della ricerca di intervalli nel Suffix Array tramite la trasformata di Burrows-Wheeler (BWT) e l’FM-index, implementato nel Burrows-Wheeler Alignment Tool (BWA).
Lo studio analizza le tecniche di hashing, strutture dati come gli alberi dei suffissi e l’integrazione di approcci basati sull'ordinamento delle sequenze.
- Introduzione al problema e Related Works: Contesto del Next Generation Sequencing e importanza del pattern matching con la presentazione di lavori presenti in letteratura.
- Approcci utili per la BWA: Analisi della Burrows-Wheeler Transform, FM-index e ottimizzazioni.
- Analisi dell'algoritmo per la ricerca di intervalli nel suffix array: Analisi delle procedure dell'algoritmo.
- Ottimizzazioni pratiche e gestione della memoria in BWA: Migliorie apportate per il Burrows-Wheeler Alignment Tool .
- Conclusioni: Importanza del BWA e confronto con altri tool(MAQ, SOAPv2 e Bowtie).
- Li et al., "Fast and accurate short read alignment with Burrows–Wheeler transform".
- Pattern Matching
- Burrows-Wheeler Alignment Tool
- Burrows-Wheeler Transform
- FM-index
- Next Generation Sequencing (NGS)
- Short Read Alignment
- Bioinformatics
- Suffix Array
- Big Data in Genomics
Questo progetto rappresenta un contributo per la comprensione e l'ottimizzazione delle tecniche di pattern matching nel campo bioinformatico, con particolare attenzione alla gestione dei dati genomici complessi. Per ulteriori dettagli, fare riferimento alla documentazione inclusa nel repository.