Pristup grubom silom
Pristup grubom silom (eng. Brute Force) [2] je najjednostavniji pristup rešavanju problema sekvenciranja antibiotika. Ovaj metod sistematski ispituje sve moguće kombinacije aminokiselina koje bi mogle formirati peptid zadate mase. Iako je ovaj pristup garantovano pronalazi tačno rešenje ako ono postoji, njegova vremenska složenost je eksponencijalna u odnosu na dužinu sekvence, što ga čini nepraktičnim za duže peptide.
Na primer, za peptid mase 579 Da, algoritam će generisati sve moguće kombinacije aminokiselina i proveriti da li njihova ukupna masa odgovara zadatoj masi. Kao što je prikazano ispod, mogu postojati različiti peptidi sa istom ukupnom masom (FPAYT i QNWGS), što dodatno komplikuje problem.
Da bi se utvrdilo koji od peptida je tačno rešenje, algoritam mora da generiše teorijski spektar za svaki kandidat peptid i uporedi ga sa eksperimentalnim spektrom. Ovo dodatno povećava računsku složenost algoritma, ali je neophodno za pronalaženje tačnog rešenja.
Naredni deo prikazuje implementaciju ovog algoritma u programskom jeziku Python.
Kod za pristup grubom silom
Algoritam na ulazu očekuje eksperimentalni spektar uređen rastuće koji uključuje 0 i masu celog peptida koji se sekvencira.
Implementacija pristupa grubom silom počinje od praznog peptida i u svakom prolasku proširuje peptide dodavanjem aminokiseline uz pomoć funkcije extends. Za svaki korak, algoritam proverava da li je masa peptida jednaka ciljanoj masi. Ako jeste, proverava se da li teorijski spektar peptida odgovara eksperimentalnom spektru. U slučaju da je teorijski spektar jednak eksperimentalnom spektru taj peptid predstavlja rešenje algoritma. U slučaju da se teorijski spektar razlikuje od eksperimentalnog kandidat nije rešenje i on se odbacuje. Ako masa peptida prelazi ciljanu masu, taj peptid se odbacuje i na taj način se obezbeđuje smanjivanje broja peptida koji se proširuje u svakom koraku. Algoritam nastavlja sa peptidima čija je masa manja od ciljane mase i u sledećem koraku ih ponovo proširuje.
def brute_force(target_spectrum)
peptides = ['']
results = []
target_peptide_mass = target_spectrum[-1]
while len(peptides) > 0:
# Proširujemo peptide aminokiselinama
extended_peptides = extend(peptides)
candidates = []
for peptide in extended_peptides:
peptide_mass = calculate_peptide_mass(peptide)
# Ako je masa jednaka traženoj masi, ovo je potencijalno rešenje
if peptide_mass == target_peptide_mass:
# Provera da li je ciklični spektar jednak traženom spektru
if cyclic_spectrum(peptide) == target_spectrum:
results.append(peptide)
# Ako je masa manja od tražene, peptid je i dalje potencijalno rešenje, inače se odbacuje
elif peptide_mass < target_peptide_mass:
candidates.append(peptide)
peptides = candidates
return results
Funkcija extends koja proširuje peptide dodavanjem aminokiselina na peptide koji su ulaz u funkciju:
def extend(peptides, amino_acid_candidates):
extended_peptides = []
for peptide in peptides:
# Svaki od peptida proširujemo aminokiselinama
for amino_acid in amino_acid_candidates:
if amino_acid != "":
extended_peptides.append(peptide + amino_acid)
return extended_peptidesFunkcija calculate_peptide_mass računa masu peptida na osnovu tabele aminokiselina i njihovih masa:
def calculate_peptide_mass(peptide):
total_mass = 0
for aa in peptide:
total_mass += AMINO_ACID_MASSES[aa]
return total_massFunkcija cyclic_spectrum računa teorijski cikličan spektar datog peptida. Razlika u odnosu na linear spektar je što ova funkcija uzima u obzir to da peptidi (npr. tirocidin) mogu biti ciklični i samim tim treba uvrstiti mase potpeptida koji počinju na krajnjim pozicijama peptida a završavaju se na početnim pozicijama.
Funkcija prvo na osnovu prefiksnih masa računa mase potpeptida i masu celog peptida. Potom prolazi kroz sam peptid i računa parcijalne mase, odnosno na osnovu prefiksnih masa (mase potpeptida) i njihovim međusobnim oduzimanjem dobija masu fragmenta u okviru peptida. Zbog uslova
if i > 0 and j < n:
spectrum.append(peptide_mass - fragment_mass)osigurava da dodaje i mase cikličnih potpeptida, odnosno od mase celog peptida oduzeće masu nekog unutrašnjeg peptida čime će dobiti masu spoljašnjeg peptida.
def cyclic_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
peptide_mass = prefix_mass[-1] # masa celog peptida
for i in range(n):
for j in range(i + 1, n + 1):
# Masa središnjeg dela peptida
fragment_mass = prefix_mass[j] - prefix_mass[i]
spectrum.append(fragment_mass)
# Uslov za proveru da li se dodaje masa potpeptida koji obuhvata kraj i početak peptida
if i > 0 and j < n:
spectrum.append(peptide_mass - fragment_mass)
spectrum.sort()
return spectrumU vizuelizaciji ispod, možete videti kako algoritam gradi stablo pretrage i kako se granama dolazi do listova drveta. 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. Pošto je ovo pristup grubom silom vizuelizacija algoritma traje dugo i ima dosta potencijalnih rešenja, preporučuje se da se unose sekvence manjih peptida da bi moglo lepo da se vidi drvo izvršavanja.
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 ipak 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:
- G: [0, 57]
- GA: [0, 57, 71, 128]