Daniel Beneš Slezská univerzita v Opavě Filozoficko-přírodovědecká fakulta Ústav informatiky
Charakteristika projektu
• On-line aplikace pro analýzu mikrosatelitů révy vinné
Charakteristika projektu
• On-line aplikace pro analýzu mikrosatelitů révy vinné • http://virtual.fpf.slu.cz/~daniel.benes
Charakteristika projektu
• On-line aplikace pro analýzu mikrosatelitů révy vinné • http://virtual.fpf.slu.cz/~daniel.benes • Navržena pro rozpoznávání směsí vín a jejich původu na základě jejich genetické struktury
Charakteristika projektu
• On-line aplikace pro analýzu mikrosatelitů révy vinné • http://virtual.fpf.slu.cz/~daniel.benes • Navržena pro rozpoznávání směsí vín a jejich původu na základě jejich genetické struktury • Využitelná například k detekci „pančovaných“ směsí vín
Charakteristika projektu
• On-line aplikace pro analýzu mikrosatelitů révy vinné • http://virtual.fpf.slu.cz/~daniel.benes • Navržena pro rozpoznávání směsí vín a jejich původu na základě jejich genetické struktury • Využitelná například k detekci „pančovaných“ směsí vín • Použitelná i pro analýzu obdobných biodat
Charakteristika projektu
• On-line aplikace pro analýzu mikrosatelitů révy vinné • http://virtual.fpf.slu.cz/~daniel.benes • Navržena pro rozpoznávání směsí vín a jejich původu na základě jejich genetické struktury • Využitelná například k detekci „pančovaných“ směsí vín • Použitelná i pro analýzu obdobných biodat • Absence podobné aplikace = důvod vzniku VITIS
Srovnání aplikací:
VITIS vs. Swiss Microsatellite Database
VITIS • Deskriptivní hledání, regulární výrazy
SVMD • Hledání podle názvu nebo abecedy
Srovnání aplikací:
VITIS vs. Swiss Microsatellite Database
VITIS • Deskriptivní hledání, regulární výrazy
SVMD • Hledání podle názvu nebo abecedy
• Hledání přednastavenými 6 mikrosatelity • Mikrosatelitní hledání, volba hodnot (je třeba znát zcela všechny hodnoty) (stačí zadat jen ty hodnoty, které znáte)
Srovnání aplikací:
VITIS vs. Swiss Microsatellite Database
VITIS
SVMD
• Deskriptivní hledání, regulární výrazy
• Hledání podle názvu nebo abecedy
• Mikrosatelitní hledání, volba hodnot
• Hledání přednastavenými 6 mikrosatelity
• Hledání směsí + odchylkové hledání
• Absence vyhledávače směsí
Srovnání aplikací:
VITIS vs. Swiss Microsatellite Database
VITIS
SVMD
• Deskriptivní hledání, regulární výrazy
• Hledání podle názvu nebo abecedy
• Mikrosatelitní hledání, volba hodnot
• Hledání přednastavenými 6 mikrosatelity
• Hledání směsí + odchylkové hledání
• Absence vyhledávače směsí
• Univerzální databáze
• Celkem 130 kultivarů (Švýcarsko)
Srovnání aplikací:
VITIS vs. Swiss Microsatellite Database
VITIS
SVMD
• Deskriptivní hledání, regulární výrazy
• Hledání podle názvu nebo abecedy
• Mikrosatelitní hledání, volba hodnot
• Hledání přednastavenými 6 mikrosatelity
• Hledání směsí + odchylkové hledání
• Absence vyhledávače směsí
• Univerzální databáze
• Celkem 130 kultivarů (Švýcarsko)
• Vícejazyčná podpora (Cz, En...)
• Jazyk: angličtina
Srovnání aplikací:
VITIS vs. Swiss Microsatellite Database
VITIS
SVMD
• Deskriptivní hledání, regulární výrazy
• Hledání podle názvu nebo abecedy
• Mikrosatelitní hledání, volba hodnot
• Hledání přednastavenými 6 mikrosatelity
• Hledání směsí + odchylkové hledání
• Absence vyhledávače směsí
• Univerzální databáze
• Celkem 130 kultivarů (Švýcarsko)
• Vícejazyčná podpora (Cz, En...)
• Jazyk: angličtina
• Úprava citlivosti hledání
Srovnání aplikací:
VITIS vs. Swiss Microsatellite Database
VITIS
SVMD
• Deskriptivní hledání, regulární výrazy
• Hledání podle názvu nebo abecedy
• Mikrosatelitní hledání, volba hodnot
• Hledání přednastavenými 6 mikrosatelity
• Hledání směsí + odchylkové hledání
• Absence vyhledávače směsí
• Univerzální databáze
• Celkem 130 kultivarů (Švýcarsko)
• Vícejazyčná podpora (Cz, En...)
• Jazyk: angličtina
• Úprava citlivosti hledání • DB administrační prostředí
Srovnání aplikací:
VITIS vs. Swiss Microsatellite Database
VITIS
SVMD
• Deskriptivní hledání, regulární výrazy
• Hledání podle názvu nebo abecedy
• Mikrosatelitní hledání, volba hodnot
• Hledání přednastavenými 6 mikrosatelity
• Hledání směsí + odchylkové hledání
• Absence vyhledávače směsí
• Univerzální databáze
• Celkem 130 kultivarů (Švýcarsko)
• Vícejazyčná podpora (Cz, En...)
• Jazyk: angličtina
• Úprava citlivosti hledání • DB administrační prostředí • Definovatelné úrovně práv
Mikrosatelitně-alelní hledací algoritmus
• Hledá v databázi všechny možné permutace vstupu
Mikrosatelitně-alelní hledací algoritmus
• Hledá v databázi všechny možné permutace vstupu • Provádí přesné množinové pokrytí
Mikrosatelitně-alelní hledací algoritmus
• Hledá v databázi všechny možné permutace vstupu • Provádí přesné množinové pokrytí • Nežádoucí efekty: – extrémní výkonová zátěž – exponenciální závislost na velikosti databáze
Mikrosatelitně-alelní hledací algoritmus
• Hledá v databázi všechny možné permutace vstupu • Provádí přesné množinové pokrytí • Nežádoucí efekty: – extrémní výkonová zátěž – exponenciální závislost na velikosti databáze • Problém řešen „prořezáním vyhledávacího stromu“
Prořezávání vyhledávacího stromu • Jedná se o vstupní filtr řazený před vyhledávací algoritmy • Minimalizuje závislost na databázi
(exponenciální → lineární)
• Spočívá v předběžném odhadu možných kandidátů • Eliminuje šumová data • Po tomto předzpracování již k výpočtu není třeba DB
Prořezávání vyhledávacího stromu • Jedná se o vstupní filtr řazený před vyhledávací algoritmy • Minimalizuje závislost na databázi
(exponenciální → lineární)
• Spočívá v předběžném odhadu možných kandidátů • Eliminuje šumová data • Po tomto předzpracování již k výpočtu není třeba DB Výsledky Původně: více jak 75 miliard mezivýsledků, desítky Nyní: tisíce mezivýsledků, časy v milisekundách
vteřin
Odchylkový hledací algoritmus • Zavádí do hledacího algoritmu definovanou chybu, tzv. „odchylku“ • Umožňuje „rozšířit“ hledání o 1 – 2 alely • Hledá kombinace odhadnutých kandidátů, které se liší od vstupního požadavku v 1 resp. 2 alelách
Odchylkový hledací algoritmus • Zavádí do hledacího algoritmu definovanou chybu, tzv. „odchylku“ • Umožňuje „rozšířit“ hledání o 1 – 2 alely • Hledá kombinace odhadnutých kandidátů, které se liší od vstupního požadavku v 1 resp. 2 alelách Důsledek • Algoritmus je schopen identifikovat směs i za předpokladu, že vstup obsahuje nepřesná data • Je šance, že se podaří identifikovat kultivar, který vlivem evoluce či nějaké mutace změnil svou genetickou strukturu (např. nalezené vzorky při archeologických vykopávkách)
Konec. (děkuji za pozornost)
