Sortie de l'algorithme pour la première séquence de `unknown.fasta`

PLAST – Primitive Local Alignment Search Tool

Projet du TP2 du cours IFT3295

Ce projet implémente PLAST, une version simplifiée de l’algorithme BLAST sans gaps, permettant de détecter rapidement des régions similaires entre une séquence nucléotidique en entrée et une banque de séquences au format FASTA. L’objectif est de reproduire les grandes étapes de BLAST en utilisant une heuristique basée sur les k-mers, l’extension gloutonne des HSPs et un système de scoring statistique.

Le programme identifie les meilleurs HSP (High Scoring Pairs) pour chaque séquence de la base, calcule leurs statistiques (score, bitscore, e-value), applique un filtrage de significativité, et retourne uniquement les meilleurs alignements significatifs.

Fonctionnalités

Le programme implémente intégralement les étapes suivantes :

Extraction des k-mers

À partir d’une graine (par défaut 11111111111), le programme extrait tous les mots de longueur k présents dans la séquence d’entrée ainsi que leurs positions.

Recherche exacte dans la base de données

Pour chaque séquence du fichier FASTA, tous les k-mers recherchés sont localisés à l’aide d’une recherche exacte.

Extension gloutonne des HSPs

Chaque HSP est étendu selon une heuristique gloutonne :

• match : +5
• mismatch : -4
• arrêt si la chute de score dépasse le seuil E

Fusion des HSPs se chevauchant

Tous les HSPs se chevauchant pour une même paire de séquences sont fusionnés selon leurs coordonnées.

Calcul du bitscore et de la e-value

Calcul selon les formules :

$$B = round\left(\dfrac{\lambda S − \ln(K)}{\ln(2)}\right)$$ $$e = m n 2^{-B}$$

avec $\lambda = 0.192$, $K = 0.176$.

Filtrage final

Pour chaque séquence, seul le meilleur HSP significatif est conservé, puis les résultats sont triés.

Format de sortie

Exemple :

>I|gat|Mesostigma_viride
# Best HSP score:78.00, bitscore:24.00, evalue: 7.67e-02
13 CGCATACGCTTGATAAGCGTA 33
23 AGTATACGCCTGATAAGCGTA 43
----------------------------------------
Total : 1

Utilisation

python src/plast.py -i SEQUENCE -db tRNAs.fasta [-E 4] [-ss 1e-3] [-seed '11111111111']

Arguments :

• -i : séquence nucléotidique à rechercher
• -db : fichier FASTA
• -E : seuil de chute du score (défaut : 4)
• -ss : seuil de significativité (défaut : 1e-3)
• -seed : graine

Structure du dépôt

.
├── data/
│   ├── tRNAs.fasta
│   └── unknown.fasta
│
├── public/
│   (ressources publiques)
│
├── results/
│   ├── Chara_vulgaris.txt
│   ├── Malus_domestica.txt
│   ├── Nephroselmis_olivacea.txt
│   ├── Phoenix_dactylifera.txt
│   └── test.txt
│
├── src/
│   ├── plast.py
│   └── utils.py
│
├── LICENSE
│
├── rapport.aux
├── rapport.log
├── rapport.pdf            # Rapport écrit pour les questions du TP
├── rapport.synctex.gz
├── rapport.tex
│
├── README.md              # Documentation du projet
├── requirements.txt       # Dépendances Python
├── run.ps1                # Script PowerShell d'exécution
└── run.sh                 # Script Bash d'exécution

Questions et analyse expérimentale

Le projet inclut :

• l’analyse de unknown.fasta
• la détermination de l’acide aminé / anticodon
• une comparaison avec BLASTN
• une étude sur l’effet des graines
• un bonus PatternHunter

Auteurs

• Josué Mongan

GitHub : Josh012006

• David Stanescu

GitHub : DavidStanescu13