Računalniška knjižnica za zavozlane strukture in aplikacije

Cilj predlaganega 3-letnega raziskovalnega projekta je razviti robustno in izvirno računalniško knjižnico za računanje z več vrstami zavozlanih struktur z aplikacijami v resničnem svetu.

Razvili bomo Python knjižnico, ki bo vsebovala glavni razred PlanarDiagram, ki bo deloval kot skupen okvir za več vrst zavozlanih struktur. Takšna podatkovna struktura bo omogočila kodiranje najrazličnejših zavozlanih struktur, kot so vozli, vozloidi, virtualni vozli, prostorski grafi, …

Glavne funkcionalnosti knjižnice bodo naslednje: orodja za manipulacijo strukture (Reidemeistrovi premiki), orodja za odkrivanje vozlov, orodja za identifikacijo vozlov (prepoznavanje vozlanega izotopskega razreda strukture s pomočjo kanonizacije in minimalizacije diagramov), izračun invariant (Alexander polinom v več spremenljivkah, Jonesov polinom, polinom HOMFLYPT, Yamadin polinom,…) in več orodij za vizualizacijo.

Razred PlanarDiagram bo prilagodljiv in razširljiv v smislu, da bo uporabnik lahko definiral lasten nabor lokalnih premikov in jih prenesel v objekt.

Razvili bomo tudi tabele zavozlanih struktur za vezoide in vezane virtualne vozle. Analizirali bomo beljakovine iz Protein Data Bank (ki jo sestavlja skoraj 200.000

vnosov) tako, da jih bomo klasificirali po njihovem tipu vezoida in tipu vezanega virtualnega vozla. Poleg tega bo na podlagi te klasifikacije narejena statistična analiza PDB.

Pokazali bomo tudi, da se knjižnica lahko uporablja tudi za preučevanje vozlov v sklenjenih, povezanih, orientabilnih 3-mnogoterostih. Takšne vozle je mogoče

enostavno predstaviti kot PlanarDiagram objekt v obliki mešanega diagrama (diagram, sestavljen iz regularne projekcije vozla znotraj Kirbyjevega diagrama 3-mnogoterosti). Implementirali bomo tudi invariante za takšne vozle (Aleksandrov polinom in modul Kauffmanovega oklepaja).

Pričakujemo, da bo naša knjižnica ena izmed osrednjih knjižnic za preučevanje teorije vozlov, zavozlanih biomolekul in vozlov v 3-mnogoterostih.

Razumevanje zavozlanosti beljakovin je ključno za določanje strukturne, funkcionalne in evolucijske vloge topologije v beljakovinskih in DNK molekulah.

DS1: načrtovanje, specifikacija in implementacije knjižnice

Knjižnica v izdelavi je javno dostopna na GitHub repozitoriju https://github.com/bgabrovsek/knotpy

DS1.1 razred PlanarDiagram (100% realizirano)

Razred PlanarDiagram je v celoti implementiran. Prav tako so implementirani podrazredi za sorodne strukture: 

• BondedKnot, OrientedBondedKnot (vezani vozel)
• Knot, OrientedKnot (klasičen vozel)
• Knotoid, OrientedKnotoid (vozloid, multispletoid)
• PlanarGraph (planarni graf)
• SpatialGraph, OrientedSpatialGraph (prostorski graf/vloen graf)
• Tangle

Poleg tega knižnica omogoča branje in pisanje struktur iz naslednjih formatov:

• EM (Ewing-Millett) notacija
• EMC (Condensed Ewing-Millett) notacija
• PD (Planar diagram) notacija
• Plantri notacija
• Native (nova notacija knjižnice KnotPy)

DP1.2: manipulacija strukture (95% realizirano)

Implementirana je večina orodij za manipulacijo struktur:

• dodajanje komponent (povezav, križišč, vozlišč)
• Reidemeistrovi premiki (I, II, III, IV, V)
• Orientacija neorientirane strukture
• Kanonična oblika planarnega diagrama

DP 1.3 Invariante (80% realizirano)

Implementirane so naslednje invariante:

• Yamadin polinom
• Kauffmanov oklepaj
• “unplugging” invarianta (v fazi testiranja)
• Bondles invarianta

DP1.4: Vizualizacija (80% realizirano)

Implementirano je grafično risanja diagramov.

DP2: tabele vozlov

DP2.1: tabele vozlov (10% realizirano)

DP2.2 analiza PDB (0% realizirano)

V izdelavi.

DP2.3: aplikacije za 3-mnogoterosti  (0% realizirano)

DP4: dokumentacija in spletno mesto (30% realizirano)

Spletno mesto je v začetnih fazah razvoja. Delovna verzija, ki še ni v celoti dokumentirana se nahaja na spletnem mestu  https://bgabrovsek.github.io/knotpy/.