FatihMSA-221201001 1.1.0

MUSCLE Multiple Sequence Alignment - Educational Implementation

FatihMSA — Çoklu Dizi Hizalaması

MUSCLE (Multiple Sequence Comparison by Log-Expectation) algoritmasının Python ile yazılmış eğitim amaçlı implementasyonu. K-mer tabanlı mesafe hesaplama, UPGMA rehber ağaç ve Needleman-Wunsch dinamik programlaması kullanarak N diziyi hizalar.

---

Kurulum

pip install FatihMSA-221201001

Ya da geliştirici modunda (kaynak koddan):

git clone <repo-url>
cd FatihMSA
pip install -e .

---

Hızlı Kullanım

Python API

from fatihmsa import run_muscle, read_fasta, write_fasta, sequences_to_list

# Ham string listesiyle
sequences = ["ATCGATCG", "ATCGTTCG", "GCTAGCTA", "GCTAACTA"]
aligned = run_muscle(sequences)

for i, seq in enumerate(aligned):
    print(f"Dizi {i}: {seq}")

# FASTA dosyasından
fasta = read_fasta("input.fasta")
ids, seqs = sequences_to_list(fasta)
aligned = run_muscle(seqs)

# Sonucu FASTA olarak kaydet
write_fasta(dict(zip(ids, aligned)), "output.fasta")

Komut Satırı (CLI)

# Sonucu ekrana yaz
fatihmsa input.fasta

# Dosyaya yaz
fatihmsa input.fasta -o output.fasta

# Adım adım ilerlemeyi göster
fatihmsa input.fasta -o output.fasta -v

Yardım:

fatihmsa --help

---

Algoritma

FatihMSA, MUSCLE algoritmasının üç aşamalı yapısını takip eder:

Aşama 1 — Taslak Hizalama

1. K-mer mesafesi: Her dizi çifti için 3-mer kümeleri çıkarılır, Jaccard uzaklığı hesaplanır:

   dist(i, j) = 1 - |kmers(i) ∩ kmers(j)| / |kmers(i) ∪ kmers(j)|
   

2. UPGMA rehber ağaç: Mesafe matrisinden hiyerarşik kümeleme yapılır. Her adımda en yakın iki küme average-linkage formülüyle birleştirilir:

   dist(new, k) = (dist(i,k) × size_i + dist(j,k) × size_j) / (size_i + size_j)
   

   Çıktı Newick formatında bir ağaç stringidir, örneğin:

   ((0:0.357,1:0.357):0.500,(2:0.357,3:0.357):0.500);
   

3. Progresif hizalama: UPGMA'nın belirlediği merge sırasına göre diziler sırayla hizalanır:

   • Dizi + Dizi → Needleman-Wunsch global hizalama
   • Dizi + Profil → Profil-dizi hizalama
   • Profil + Profil → Profil-profil hizalama

Aşama 2 — İyileştirme

Taslak hizalamadan elde edilen profiller üzerinden mesafe matrisi yeniden hesaplanır, rehber ağaç güncellenir ve hizalama tekrarlanır. Bu aşama, ilk taslaktaki hataları düzeltmeye yöneliktir.

Not: Bu implementasyonda aşama 2 basitleştirilmiş biçimde uygulanmıştır.

Aşama 3 — Rafine Etme

Profil-profil hizalama kullanılarak hizalanmış sütunlar yeniden değerlendirilir. Her sütun, karakter frekanslarından oluşan bir vektördür:

# Örnek profil sütunu
{'A': 0.5, 'G': 0.25, '-': 0.25}

İki profil sütunu arasındaki skor ağırlıklı ortalama ile hesaplanır:

match_score(col1, col2) = Σ freq1[c1] × freq2[c2] × score(c1, c2)

---

Puanlama Parametreleri

Durum	Skor
Eşleşme	+1
Uyumsuzluk	−1
Boşluk (gap)	−2

Parametreler needleman_wunsch() fonksiyonu üzerinden özelleştirilebilir:

from fatihmsa.align import needleman_wunsch
a1, a2 = needleman_wunsch("ATCG", "ATTG", match=2, mismatch=-1, gap=-3)

---

Desteklenen Formatlar

Ham String Listesi

sequences = ["ATCGATCG", "GCTAGCTA"]
aligned = run_muscle(sequences)

• Büyük/küçük harf fark etmez (otomatik büyük harfe çevrilir)
• Geçerli karakterler: A, T, C, G, N

FASTA Formatı

>seq1
ATCGATCG
>seq2
ATCGTTCG
>seq3
GCTAGCTA

Dosyadan veya doğrudan string olarak okunabilir:

from fatihmsa import read_fasta

# Dosyadan
fasta = read_fasta("input.fasta")

# Doğrudan string
fasta = read_fasta(">seq1\nATCGATCG\n>seq2\nATCGTTCG\n")

---

Proje Yapısı

FatihMSA/
├── fatihmsa/
│   ├── __init__.py      # Dışa aktarılan fonksiyonlar
│   ├── align.py         # Needleman-Wunsch global hizalama
│   ├── cli.py           # Komut satırı arayüzü (argparse)
│   ├── distance.py      # K-mer mesafesi + UPGMA rehber ağaç
│   ├── io.py            # FASTA okuma/yazma
│   └── main.py          # Progresif MSA orkestratörü
├── tests/
│   ├── test_align.py    # Hizalama testleri
│   ├── test_distance.py # Mesafe ve UPGMA testleri
│   └── test_main.py     # Uçtan uca MSA testleri
├── pyproject.toml
├── setup.py
└── README.md

Testleri çalıştırmak için:

pytest tests/ -v

---

Geliştirici

Alan	Bilgi
Ad Soyad	Fatih Yilmazer
Öğrenci No	221201001
Ders	Biyoinformatik
Paket Adı	FatihMSA-221201001
Versiyon	1.0.0