Sekvenciranje antibiotika

Leaderboard algoritam [2] je optimizovani pristup za sekvenciranje peptida. Za razliku od sekvenciranja grubom silom koje zahteva tačno poklapanje između teorijskog spektra kandidata i eksperimentalnog spektra, ovaj algoritam je dizajniran da radi sa nedostajućim i lažnim masama tako što prati samo najbolje kandidate peptida umesto svih mogućnosti.

U realnim eksperimentalnim podacima masene spektrometrije, izmereni eksperimentalni spektar je često zašumljen i nepotpun. Neki očekivani fragmenti peptida mogu nedostajati, a lažni pikovi se mogu pojaviti zbog pozadinskog šuma. Savršeno poklapanje između teorijskog spektra peptida i eksperimentalnog spektra je malo verovatno.

Prednosti Algoritma

Efikasnost

Fokusira se samo na najperspektivnije kandidate, značajno smanjujući vreme izvršavanja

Skalabilnost

Efikasno radi sa peptidima različitih dužina bez eksponencijalnog rasta vremena

Preciznost

Održava visoku tačnost uprkos šumu u eksperimentalnim podacima

Primene

Eksperimentalni Podaci

Idealan za analizu realnih podataka masene spektrometrije sa šumom

Nepotpuni Podaci

Kada tačno poklapanje nije moguće zbog nepotpunih ili netačnih podataka u spektru

Vremenski Kritične Analize

Kada je potrebna brza identifikacija peptida iz velikih skupova podataka

Kod za Leaderboard algoritam

Algoritam održava listu najboljih kandidata (leaderboard) i u svakoj iteraciji proširuje samo najperspektivnije peptide. Ovo značajno smanjuje prostor pretrage u poređenju sa pristupom grube sile. Za svaki od peptida koji se generiše određujemo koji je njegov score, odnosno broj masa linearnog spektra peptida koji je jednak masama u eksperimentalnom spektru.

def leaderboard_sequencing(target_spectrum):
    # Krećemo od praznog peptida
    peptides = ['']

    # Peptid koji je trenutno najbolji kandidat i njegov score
    leader_peptide = ''
    leader_peptide_score = 0

    target_peptide_mass = target_spectrum[-1]

    while len(peptides) > 0:
        extended_peptides = extend(peptides, amino_acid_candidates)

        consistent_peptides = []

        for peptide in extended_peptides:
            peptide_mass = calculate_peptide_mass(peptide)
            if peptide_mass == target_peptide_mass:
                # Računamo koji je broj poklapanja cikličnog peptida sa eksperimentalnim spektrom
                peptide_score = cyclic_score(peptide, target_spectrum)
                # Ako je score bolji, ažuriramo vrednost najboljeg kandidata
                if peptide_score > leader_peptide_score:
                    leader_peptide = peptide
                    leader_peptide_score = peptide_score
            elif peptide_mass < target_peptide_mass:
                consistent_peptides.append(peptide)

        # Funkcija u kojoj se pravi lista kandidata i vraćaju samo najbolji kandidati
        peptides = trim(consistent_peptides, target_spectrum, MAX_NUMBER_OF_CANDIDATES)

    return leader_peptide

Jedna od glavnih funkcija je trim. Ulaz u funkciju predstavljaju peptidi koji su kandidati za rešenje, eksperimentalni spektar kao i broj peptida koji ćemo vratiti iz funkcije odnosno najbolji kandidati za potencijalno rešenje. Bitno je izabrati dobro broj kandidata koji prolazi u dalju rundu. U slučaju da je taj broj previše mali rizujemo da previše agresivno odsečemo neke kandidate i da potencijalno izgubimo rešenje. U slučaju da je borj previše veliki čuvaćemo previše kandidata i samim tim povećati vreme izvršavanja algoritma. Generalno, dobra je praksa ako se traže peptidi sa manjom masom da se koristi manji broj kandidata koji nastavlja u sledeću rundu a ako se masa poveća da se samim tim poveća i broj kandidata koji nastavlja u sledeću rundu.

def trim(peptides, target_spectrum, max_number_of_candidates):
    # Ako je broj peptida manji od broja kandidata koji može da prođe
    # u sledeću rundu, vraćamo sve peptide
    if len(peptides) <= max_number_of_candidates:
        return peptides

    leaderboard = []

    # Za svaki od peptida računamo njegov score
    for peptide in peptides:
        # Bitno je koristiti linear_score funkciju jer ovo nije finalni izgled peptida
        # samim tim, ako se koristi cyclic_score možemo da dobijemo mase koje možda neće
        # postojati kada se peptid proširi
        peptide_score = linear_score(peptide, target_spectrum)
        leaderboard.append((peptide_score, peptide))

    # Sortiramo listu peptida u opadajućem redosledu po njihovom score-u
    leaderboard.sort(reverse=True)

    # Ako u listi kandidata ima još neka sekvenca peptida čiji je 
    # score jednak poslednjoj sekvenci koja prolazi u sledeću rundu,
    # dodajemo i tu sekvencu da potencijalno ne bismo izgubili dobro
    # rešenje 
    for i in range(max_number_of_candidates, len(leaderboard)):
        if leaderboard[i][0] < leaderboard[max_number_of_candidates - 1][0]:
            break

    # Lista kandidata koja je prošla u sledeću rundu
    trimmed_leaderboard = leaderboard[:i]
    # Pošto smo u listi čuvali peptide sa njihovim rezultatima,
    # vraćamo samo listu peptida odnosno njihove sekvence
    return [el[1] for el in trimmed_leaderboard]

Funkcija cyclic_score računa broj poklapanja teorijskog spektra cikličnog peptida sa eksperimentalnim spektrom. Ova funkcija se koristi u slučaju da je masa peptida jednaka najvećoj teoorijskoj masi jer je u tom slučaju formiran ceo peptid i mogu da se nađu svi potpeptidi.

def cyclic_score(peptide, target_spectrum):
    # Formira se ciklični spektar i na osnovu njega se računa score
    peptide_cyclic_spectrum = cyclic_spectrum(peptide)
    return score(peptide_cyclic_spectrum, target_spectrum)

Funkcija linear_score računa broj poklapanja teorijskog spektra peptida sa eksperimentalnim spektrom. Ova funkcija se koristi kada se ceo peptid još ne zna i samim tim ne mogu da se kreiraju sve ciklične varijacije jer bi se dobile mase koje se možda ne bi dobile kada se peptid proširi aminokiselinama.

def linear_score(peptide, target_spectrum):
    # Formira se linearni spektar i na osnovu njega se računa score
    peptide_linear_spectrum = linear_spectrum(peptide)
    return score(peptide_linear_spectrum, target_spectrum)

Funkcija score računa broj poklapanja teorijskog spektra peptida sa eksperimentalnim spektrom.

def score(peptide_spectrum, target_spectrum):
    total_score = 0

    i = 0
    j = 0
    n = len(peptide_spectrum)
    m = len(target_spectrum)

    # Prolazi se kroz spektre i upoređuju mase
    while i < n and j < m:
        # Ako su mase jednake prelazimo na sledeće mase u oba spektra i uvećavamo broj poklapanja
        if peptide_spectrum[i] == target_spectrum[j]:
            i += 1
            j += 1
            total_score += 1
        # U slučaju da je masa teorijskog spektra veća, prelazimo na sledeću masu u eksperimentalnom spektru
        elif peptide_spectrum[i] > target_spectrum[j]:
            j += 1
        # U slučaju da je masa teorijskog spektra manja, prelazimo na sledeću masu u teorijskom spektru
        else:
            i += 1

    return total_score

U vizuelizaciji ispod, možete videti kako algoritam kroz runde bira N kandidata koji prolaze u sledeću rundu. Takođe, možete da vidite teorijske spektre kandidata kao i broj elemenata spektra koji su isti kao i u zadatom teorijskom spektru. Teorijski spektri kandidata mogu da se zumiraju da bi se lakše videli potpeptidi sa njihovim masama.
U poslednjoj rundi ć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.
Dodatno, ako ne želite da vidite runde koje su se desile potrebno je da označite opciju da se prikažu samo rešenja.

Primeri peptida i njihovih teorijskih spektara:

NQE: [0, 114, 128, 129, 242, 243, 257, 371]
NQEL: [0, 113, 114, 128, 129, 227, 240, 242, 257, 355, 356, 370, 370, 484]

Leaderboard Algoritam