Branch and Bound Algoritam
Branch and Bound algoritam [2] je optimizovana verzija pristupa grubom silom koja koristi strategiju "podeli pa vladaj" za efikasnije pretraživanje prostora rešenja. Za razliku od pristupa grubom silom koji ispituje sve moguće kombinacije, Branch and Bound algoritam inteligentno eliminiše delove prostora pretrage koji ne mogu sadržati optimalno rešenje.
U kontekstu sekvenciranja peptida, algoritam funkcioniše na sledeći način:
- Grananje (Branch): Algoritam gradi stablo pretrage gde svaki čvor predstavlja delimičnu sekvencu peptida. Svaki čvor se grana dodavanjem nove aminokiseline na postojeću sekvencu.
- Ograničavanje (Bound): Za svaki čvor, algoritam procenjuje da li taj put može dovesti do validnog rešenja. Ako masa peptida već premašuje ciljanu masu, ili ako teorijski spektar delimične sekvence peptida nije konzistentan sa eksperimentalnim, ta grana se "odseca" i dalje ne istražuje.
- Optimizacija: Algoritam može koristiti dodatne heuristike za procenu koje grane prvo istražiti, što dodatno ubrzava pronalaženje rešenja.
Prednosti Branch and Bound algoritma u odnosu na pristup grubom silom su značajne:
Pristup grubom silom
- Istražuje sve moguće kombinacije
- Eksponencijalna vremenska složenost
- Garantuje pronalaženje svih rešenja
- Neefikasan za duže peptide
Branch and Bound
- Inteligentno eliminiše neperspektivne grane
- Značajno bolja vremenska složenost (u najgorem slučaju je i dalje eksponencijalne složenosti ali i dalje dosta brži)
- I dalje garantuje pronalaženje svih rešenja
- Efikasniji za duže peptide
Kod za Branch and Bound algoritam
Algoritam na ulazu očekuje eksperimentalni spektar uređen rastuće koji uključuje 0 i masu celog peptida koji se sekvencira. Za razliku od pristupa grubom silom, Branch and Bound algoritam koristi dodatne provere da bi eliminisao neperspektivne grane što ranije.
def branch_and_bound(target_spectrum):
peptides = ['']
results = []
target_peptide_mass = target_spectrum[-1]
while len(peptides) > 0:
extended_peptides = extend(peptides)
candidates = []
for peptide in extended_peptides:
peptide_mass = calculate_peptide_mass(peptide)
if peptide_mass == target_peptide_mass:
if cyclic_spectrum(peptide) == target_spectrum:
results.append(peptide)
elif peptide_mass < target_peptide_mass:
# Branch and Bound optimizacija: provera da li je peptid konzistentan sa spektrom
if is_consistent_with_spectrum(peptide, target_spectrum):
candidates.append(peptide)
# Ako nije konzistentan, ova grana se "odseca" i ne istražuje dalje
peptides = candidates
return resultsKljučna razlika u odnosu na pristup grubom silom je funkcija is_consistent_with_spectrum koja proverava da li je trenutni peptid konzistentan sa ciljnim spektrom:
def is_consistent_with_spectrum(peptide, target_spectrum):
# Generiši linearni spektar peptida
peptide_spectrum = linear_spectrum(peptide)
i = 0
j = 0
n = len(peptide_spectrum)
m = len(target_spectrum)
# Provera da li se svaka masa u okviru peptide_spectrum javlja i u okviru target_spectrum.
# Ako neka masa postoji u okviru peptide_spectrum a ne u okviru target_spectrum to znaci da spektrum nije konzistentan,
# obrnuto ne mora da važi, jer se računaju spektar parcijalnog peptida a ne još celog pa masa koja fali može da se pojavi.
while i < n and j < m:
if peptide_spectrum[i] == target_spectrum[j]:
i += 1
j += 1
elif peptide_spectrum[i] > target_spectrum[j]:
j += 1
else:
return False
if i < n:
return False
else:
return TrueFunkcija linear_spectrum računa linearni spektar peptida, što je brže od računanja cikličnog spektra:
def linear_spectrum(peptide):
n = len(peptide)
prefix_mass = [0 for _ in range(n + 1)]
for i in range(n):
amino_acid = peptide[i]
prefix_mass[i + 1] = prefix_mass[i] + AMINO_ACID_MASSES[amino_acid]
spectrum = [0] # Masa praznog peptida
for i in range(n):
for j in range(i + 1, n + 1):
fragment_mass = prefix_mass[j] - prefix_mass[i]
spectrum.append(fragment_mass)
spectrum.sort()
return spectrumU vizuelizaciji ispod, možete videti kako algoritam gradi stablo pretrage i kako eliminiše grane koje ne mogu dovesti do rešenja jer teorijski spektar nije konzistentan. Zeleni čvorovi predstavljaju potencijalna rešenja, crveni čvorovi su eliminisani, a plavi čvor je trenutno aktivan u pretrazi. Takođe drvo može da se zumira i pomera da bi lakše mogli da se vide svi čvorovi.
Na kraju će biti prikazani peptidi koji predstavljaju najbolje kandidate za rešenje. Može imati više različitih kandidata s obzirom da različite aminokiseline mogu da imaju istu masu.
Ako želite da unesete neke sekvence koje su duže kliknite na dugme da se prikažu samo rešenja. Zahvaljujući ovoj opciji, neće se prikazati drvo izvršavanja algoritma i samim tim biće omogućeno brzo prikazivanje samih kandidata za traženi spektar.
Primeri peptida i njihovih teorijskih spektara:
- GA: [0, 57, 71, 128]
- NQE: [0, 114, 128, 129, 242, 243, 257, 371]