Simple view
Full metadata view
Authors
Statistics
Optymalizacja czasowa i pamięciowa algorytmu Needlemana-Wunscha
Time and memory optimization of Needleman-Wunsch algorithm
dopasowanie sekwencji, algorytm Needlemana-Wunscha, algorytm Hirschberga, metoda czterech Rosjan, programowanie dynamiczne, złożoność obliczeniowa, optymalizacja, wydajność
sequence alignment, Needleman-Wunsch algorithm, Hirschberg’s algorithm, method of four Russians, dynamic programming, computational complexity, optimization, efficiency
Standardowym sposobem znajdowania dopasowania sekwencji jest algorytm Needlemana-Wunscha, który charakteryzuje się kwadratową złożonością czasową i pamięciową. Istnieją jednak metody pozwalające na efektywniejsze rozwiązanie tego problemu – algorytm Hirschberga, wymagający jedynie liniowej ilości pamięci oraz metoda czterech Rosjan – ogólna technika przyspieszania programowania dynamicznego, umożliwiająca obniżenie złożoności czasowej o czynnik logarytmiczny. W niniejszej pracy zaimplementowano w języku Julia podstawową wersję algorytmu, a także obie alternatywy, a następnie dokonano analizy porów-nawczej pod względem czasu wykonania programu i faktycznego zużycia pamięci. Skupiono się również na optymalizacji na poziomie języka programowania, po uprzednim zestawieniu jego wydajności z językami C/C++ i Fortran.Praca została ukierunkowana na zbadanie praktyczności omawianych podejść w kontekście realnego zastosowania – z użyciem danych biologicznych dużych rozmiarów, a także konfrontację teorii złożoności obliczeniowej z rzeczywistą wydajnością.
A standard way of finding sequence alignment is by Needleman-Wunsch algorithm, whose both time and space complexity is quadratic. However, there are methods for solving the problem more effectively – Hirschberg algorithm, which requires only linear space and the method of four Russians – a general technique for speeding up dynamic programming that allows to reduce the running time by a logarithmic factor. In this thesis, the basic version and the two improvements were implemented using Julia programming language. An analysis was per-formed to compare execution time and actual memory usage. Also, optimization on the programming language level was taken into account after collation with C/C++ and Fortran languages. The thesis focuses on examining practicality of the discussed approaches in a context of real application – with a big biological data input and also on confronting the computational complexity theory with actual efficiency.
| dc.abstract.en | A standard way of finding sequence alignment is by Needleman-Wunsch algorithm, whose both time and space complexity is quadratic. However, there are methods for solving the problem more effectively – Hirschberg algorithm, which requires only linear space and the method of four Russians – a general technique for speeding up dynamic programming that allows to reduce the running time by a logarithmic factor. In this thesis, the basic version and the two improvements were implemented using Julia programming language. An analysis was per-formed to compare execution time and actual memory usage. Also, optimization on the programming language level was taken into account after collation with C/C++ and Fortran languages. The thesis focuses on examining practicality of the discussed approaches in a context of real application – with a big biological data input and also on confronting the computational complexity theory with actual efficiency. | pl |
| dc.abstract.pl | Standardowym sposobem znajdowania dopasowania sekwencji jest algorytm Needlemana-Wunscha, który charakteryzuje się kwadratową złożonością czasową i pamięciową. Istnieją jednak metody pozwalające na efektywniejsze rozwiązanie tego problemu – algorytm Hirschberga, wymagający jedynie liniowej ilości pamięci oraz metoda czterech Rosjan – ogólna technika przyspieszania programowania dynamicznego, umożliwiająca obniżenie złożoności czasowej o czynnik logarytmiczny. W niniejszej pracy zaimplementowano w języku Julia podstawową wersję algorytmu, a także obie alternatywy, a następnie dokonano analizy porów-nawczej pod względem czasu wykonania programu i faktycznego zużycia pamięci. Skupiono się również na optymalizacji na poziomie języka programowania, po uprzednim zestawieniu jego wydajności z językami C/C++ i Fortran.Praca została ukierunkowana na zbadanie praktyczności omawianych podejść w kontekście realnego zastosowania – z użyciem danych biologicznych dużych rozmiarów, a także konfrontację teorii złożoności obliczeniowej z rzeczywistą wydajnością. | pl |
| dc.affiliation | Wydział Fizyki, Astronomii i Informatyki Stosowanej | pl |
| dc.area | obszar nauk ścisłych | pl |
| dc.contributor.advisor | Romańczukiewicz, Tomasz - 147959 | pl |
| dc.contributor.author | Nowogórski, Dominik | pl |
| dc.contributor.departmentbycode | UJK/WFAIS | pl |
| dc.contributor.reviewer | Romańczukiewicz, Tomasz - 147959 | pl |
| dc.contributor.reviewer | Cieśla, Michał - 101020 | pl |
| dc.date.accessioned | 2020-07-28T01:18:29Z | |
| dc.date.available | 2020-07-28T01:18:29Z | |
| dc.date.submitted | 2019-06-27 | pl |
| dc.fieldofstudy | informatyka | pl |
| dc.identifier.apd | diploma-134088-225560 | pl |
| dc.identifier.project | APD / O | pl |
| dc.identifier.uri | https://ruj.uj.edu.pl/xmlui/handle/item/236335 | |
| dc.language | pol | pl |
| dc.subject.en | sequence alignment, Needleman-Wunsch algorithm, Hirschberg’s algorithm, method of four Russians, dynamic programming, computational complexity, optimization, efficiency | pl |
| dc.subject.pl | dopasowanie sekwencji, algorytm Needlemana-Wunscha, algorytm Hirschberga, metoda czterech Rosjan, programowanie dynamiczne, złożoność obliczeniowa, optymalizacja, wydajność | pl |
| dc.title | Optymalizacja czasowa i pamięciowa algorytmu Needlemana-Wunscha | pl |
| dc.title.alternative | Time and memory optimization of Needleman-Wunsch algorithm | pl |
| dc.type | licenciate | pl |
| dspace.entity.type | Publication |