Skip to content

Latest commit

 

History

History
110 lines (77 loc) · 2.59 KB

README.md

File metadata and controls

110 lines (77 loc) · 2.59 KB

🧬 Sequence Alignment - Bioinformatics

Implementation of classic sequence alignment algorithms in Python for DNA sequence comparison.

📋 Description

This project implements the two fundamental algorithms for biological sequence alignment:

  • Needleman-Wunsch (Global Alignment) - Aligns entire sequences end-to-end
  • Smith-Waterman (Local Alignment) - Finds the best matching subsequences

🚀 Features

  • ✅ Read sequences from FASTA files
  • ✅ Global alignment with Needleman-Wunsch algorithm
  • ✅ Local alignment with Smith-Waterman algorithm
  • ✅ Backtracking to extract optimal alignments
  • ✅ Score matrix visualization
  • ✅ Validated against EMBOSS Needle & Water tools

📁 Project Structure

sequence-alignment-bioinformatics/
├── alignment.py        # Main Python script with all algorithms
├── sequences.fasta     # Sample DNA sequences in FASTA format
└── README.md           # This file

🔧 Requirements

  • Python 3.x
  • NumPy
pip install numpy

💻 Usage

python alignment.py

Example Output

Séquence 1: ATGCGTACGTTAGC
Séquence 2: ATGCCGTCGTTAGG

============================================================
         ALIGNEMENT GLOBAL (Needleman-Wunsch)
============================================================

Score final: 10

=== Alignement Global ===
Seq1: ATGCGTACGTTAGC
Seq2: ATGCCGTCGTTAGG

============================================================
          ALIGNEMENT LOCAL (Smith-Waterman)
============================================================

Score maximal: 10

=== Alignement Local ===
Seq1: ATGCGTACGTTAG
Seq2: ATGCCGTCGTTAG

⚙️ Parameters

Default scoring scheme:

Parameter Value
Match +1
Mismatch 0
Gap -1

You can modify these parameters in the function calls:

matrix = score_matrix_alignement_global(seq1, seq2, match=2, mismatch=-1, gap=-2)

📊 Algorithms

Needleman-Wunsch (Global)

  • Initializes borders with gap penalties
  • Fills matrix using dynamic programming
  • Backtracking from bottom-right corner

Smith-Waterman (Local)

  • Initializes borders with zeros
  • Minimum score is 0 (never goes negative)
  • Backtracking from maximum score position until reaching 0

🔗 Validation

Results validated against professional tools:

👤 Author

EL ALEM YOUSSEF

📄 License

This project is for educational purposes - Bioinformatics TP3.