A legrövidebb közös szuperszó probléma közelítő algoritmusainak implementációi

OData támogatás
Konzulens:
Dr. Csima Judit
Számítástudományi és Információelméleti Tanszék

A bioinformatika egyik fontos ága a DNS szekvenálás. Az új generációs genomszekvenálási technológiák az egyre kifinomultabb laboratóriumi eljárások mellett a modern számítástechnika számítási kapacitását használják ki a hatékony szekvenálás érdekében.

Az egyik legelterjedtebb DNS szekvenálási módszer az úgynevezett shotgun szekvenálás. Ennek lényege, hogy nem a nehezen beolvasható teljes szekvenciát olvassák be, hanem átfedésben álló, rövid részleteit, azaz fragmenseit. Az eredeti szekvencia ezekből való meghatározását nevezzük legrövidebb közös szuperszó problémának, mely NP-teljes probléma lévén algoritmikailag nehezen megoldható, a megoldáshoz közelítő algoritmusok használatosak.

Két ilyen közelítés a mohó algoritmus és az úgynevezett körfedéses algoritmus. Mindkét közelítő algoritmus során felmerülő részprobléma az összes szuffix-prefix pár probléma, melynek naiv megoldása rendkívül költséges, a hatékony megoldáshoz a szóhalmaz előzetes feldolgozására és speciális adatszerkezetekre van szükség. Ilyen adatszerkezet a szuffix-fa, a szuffix-tömb és a prefix-fa.

Jelen diplomaterv célja a legrövidebb közös szuperszó problémát megoldó közelítő algoritmusok vizsgálata és hatékony implementációja a már említett adatszerkezetekkel, illetve ezen implementációk összehasonlítása.

Letölthető fájlok

A témához tartozó fájlokat csak bejelentkezett felhasználók tölthetik le.