Best paper za prezentaci nového algoritmu
Výzkumná skupina doc. Michala Kouckého z MFF UK získala jedno z hlavních ocenění udílených v rámci prestižní konference FOCS. Algoritmus, který vědci vyvinuli, by mj. mohl zpřesnit a urychlit výzkum v oblasti genetiky.
Ocenění „best paper“ vynesla pětičlennému týmu práce Approximating Edit Distance Within Constant Factor in Truly Sub-Quadratic Time. Doc. Michal Koucký (Informatický ústav UK), jeho studentka Debarati Das, postdoci Elazar Goldenberg (nyní na Academic College of Tel Aviv-Yaffo) a Diptarka Chakraborty (nyní na Weizmann Institute of Science) a prof. Mike Saks (Rutgers University) v ní představili nový algoritmus pro měření podobnosti textů.
Tzv. editační vzdálenost má řadu využití, mj. v bioinformatice, kde slouží pro měření podobnosti řetězců DNA a bílkovin. Kvůli praktické uplatnitelnosti se pro ni hledají stále efektivnější algoritmy. „Nejlepší algoritmus pro přesné spočítání editační vzdálenosti má tzv. kvadratickou časovou složitost, což ale fakticky znamená, že na příliš dlouhých řetězcích běží příliš pomalu. Z tohoto důvodu se v praxi používají různé heuristiky,“ vysvětluje doc. Koucký.
Jeho skupině se jako vůbec první podařilo vyvinout algoritmus, který dává odhad s garantovanou konstantní přesností (multiplikativní odchylkou) a pracuje v čase lepším než kvadratickém. „Mnozí lidé se domnívali, že takový algoritmus nemusí ani existovat. Opak je ale pravdou. Naše technika může vést ke zrychlení a zpřesnění výpočtu této pro praxi důležité míry,“ dodává doc. Koucký.
FOCS (Annual IEEE Symposium on Foundations of Computer Science) patří k nejstarším a nejprestižnějším konferencím zaměřeným na teoretickou informatiku. Výzkumný tým si ocenění převzal v Paříži, kde letošní ročník ve dnech 7. – 9. října probíhal. „Samozřejmě nás toto uznání těší. Znamená to, že se soustředíme na správné otázky a problémy,“ říká doc. Koucký.
– OPMK –
