AlgOptBio

Obiectivele generale urmărite.

În cadrul acestui proiect ne concentrăm eforturile asupra diverselor variante de probleme pe șiruri de caractere, cu aplicații importante și variate e.g. compresia datelor, biologie computațională, medicină. Deoarece ADN-ul este o secvență de litere din alfabetul A, C, G, T, multe din problemele de genomică se pot formula ca probleme pe șiruri de caractere. Un exemplu clasic este problema celui mai scurt superșir comun (eng. shortest common superstring), prescurtată SCS, ce are ca input un set de șiruri, iar scopul este găsirea celui mai scurt șir care este un superșir al tuturor șirurilor din datele de intrare. Problema SCS are o multitudine de aplicații importante, precum asamblarea genomului, compresia datelor, și planificare (eng. scheduling).

Scopul acestui proiect este să dezvoltăm algoritmi de aproximare sau să demonstrăm limite inferioare de complexitate pentru probleme similare cu cea prezentată mai sus și pentru variante ale lor (e.g. când alfabetul sau lungimea șirurilor din input sunt limitate).