Polynomisesti ratkeavat ongelmat valtavilla verkoilla ovat käytännössä ratkeavia vain, jos niiden aikavaativuus on riittävän matala. Myös NP-kovat ongelmat, joille on olemassa ratkaisija, ovat käytännössä ratkeavia vain tarpeeksi pienille syötteille. Laajennamme näitä kahta käytännön ratkeavuuden rajaa, jotka liittyvät kahteen bioinformatiikan keskeiseen sovellukseen. Pangenominen verkko esittää geneettisen muuntelun populaatiossa. Kehitämme näille verkoille algoritmeja, joiden aikavaativuus on lineaarinen suhteessa syötteeseen ja mahdollisesti ylilineaarinen suhteessa johonkin syötteen pienikokoiseen parametriin. Transkriptomiikan NP-kovissa ongelmissa käytämme virtausverkkoja ja yksinkertaistamme näiden ongelmien syötteitä turvallisilla alipoluilla. Tuloksemme tulevat nopeuttamaan merkittävästi bioinformatiikan menetelmiä ja mahdollistavat niiden käytön suuremmille syötteille. Tuloksiamme voidaan soveltaa verkko-ongelmiin myös muilla aloilla.

2024

2026