Filogenetikus fák építése nem szimmetrikus hasonlósági mérték alkalmazásával

Busa-Fekete Róbert¹, Kocsor András¹, Bagyinka Csaba²

¹MTA-SZTE Mesterséges Intelligencia Kutatócsoport
6720, Szeged, Aradi vértanúk tere 1.

²MTA SZBK Biofizikai Intézet
6701, Szeged, Postafiók 521.

A különböző fajokból izolált fehérjék szekvenciáinak összehasonlítási lehetősége új típusú vizsgálatok elvégzésére adott alapot a filogenetikában, ami merőben átformálta a biológia ezen ágát. Míg korábban a filogenetika egyet jelentett a fajok evolúciós fejlődéstanával, addig az új eredmények hatására a kutatások kiterjedtek a fehérjék öröklődésének vizsgálatára. A filogenetika alapfeladata matematikai szemszögből egy jóldefiniált probléma, egy helyes fatopológiát kell hozzárendelnünk a különböző fajokból izolált, hasonló funkciójú és hasonló szekvenciájú fehérjékhez távolságviszonyaik alapján. A feladat az úgynevezett NP-teljes problémák közé tartozik, amely problémaosztály elemeinek megoldására egyelőre nem létezik polinomiális időben kiszámítható algoritmus. Ezért heurisztikus algoritmusok kidolgozása szükséges a feladat gyakorlati megoldásához. Ebben a publikációban az agglomeratív eljárások kiterjeszthetőségét vizsgáljuk nem szimmetrikus hasonlósági mértékekre. Az első továbbfejlesztett módszer az egyik jól ismert klaszterező eljárás, az Unweighted Pair Group Method with Arithmetic Mean (UPGMA). Továbbá definiálunk egy újszerű módszert, ami a K legjobb fatopológiát tárolja keresés közben. A megoldás-kezdeményeket a legkisebb négyzetek problémával rangsoroljuk. Majd a mesterséges intelligencia területén közismert úgynevezett multi-stack módszerrel a megoldástér lényegesen nagyobb részét járhatjuk be.  A javasolt módszerek végrehajtása során a nem szimmetrikus hasonlósági mértéket adott két fehérjére, az őket szintetizáló DNS szekvenciák Kolmogorov komplexitásának közelítésével határozhatjuk meg.