Habilitačná prednáška

Tue 11 Mar. 2014, 13:00
C

Title: Hľadanie podobností vo veľkých databázach biologických sekvencií
Speaker: Broňa Brejová

Základným nástrojom bioinformatiky je hľadanie podobností medzi
sekvenciami DNA a proteínov, na čo potom nadväzuje veľké množstvo
ďalších analýz. Z informatického hľadiska ide o hľadanie podslov,
ktoré majú navzájom malú editačnú vzdialenosť. V súčasnosti je
potrebné túto úlohu riešiť v obrovských databázach, čo vedie k vývoju
nových algoritmických techník. Základným prístupom je algoritmus
dynamického programovania na výpočet editačnej vzdialenosti, ktorý ale
pracuje v kvadratickom čase a pre veľké databázy je teda príliš
pomalý. V praxi sa často používajú heuristiky, ktoré rýchlo
identifikujú relevantné častí databázy, a tieto sa potom prehľadajú
presným algoritmom. Niektoré z týchto heuristík sú založené na
elegantných pravdepodobnostných alebo kombinatorických konštruktoch.
Aktuálnym trendom je tiež vyvíjať algoritmy, ktoré pracujú priamo s
komprimovaným textom a tým dosahujú časovú aj pamäťovú úsporu.