Knowledge base: Warsaw University of Technology

Settings and your account

Back

Project and implemenation of algorithm design to correct third generation sequencer reads

Patryk Pankiewicz

Abstract

This thesis describes algorithm for correction third generation sequencing reads. Such reads have high error rate (around 20% incorrect symbols). Implemented application „DNAcorr” provides following modules: — finding similarities between DNA sequences; — correction of DNA sequences with high error rate. First module can produce output similar to the most common and widely used algorithms dedicated for this purpose by using well-adjusted parameters. It can be used for second and third generation DNA sequences. Second module can correct high error rate DNA sequences by detecting similarities with low error rate DNA sequences and finding consensus. Algorithm for finding similarities uses effective data structures for storing DNA sequences information. Application have simple command line interface and has been implemented using C++ with Boost libraries. ”DNAcorr” uses threads that reduces run time of both modules. Application has been tested on simulated data.
Diploma type
Engineer's / Bachelor of Science
Diploma type
Engineer's thesis
Author
Patryk Pankiewicz (FEIT/ICS) Patryk Pankiewicz,, The Institute of Computer Science (FEIT/ICS)Faculty of Electronics and Information Technology (FEIT)
Title in Polish
Projekt i implementacja algorytmu do korekcji odczytów z sekwenatorów trzeciej generacji
Supervisor
Robert Marek Nowak (FEIT/ICS) Robert Marek Nowak,, The Institute of Computer Science (FEIT/ICS)Faculty of Electronics and Information Technology (FEIT)
Certifying unit
Faculty of Electronics and Information Technology (FEIT)
Affiliation unit
The Institute of Computer Science (FEIT/ICS)
Study subject / specialization
, Informatyka (Computer Science)
Language
(pl) Polish
Status
Finished
Defense Date
26-06-2019
Issue date (year)
2019
Internal identifier
71/19 (2664)
Reviewers
Robert Marek Nowak (FEIT/ICS) Robert Marek Nowak,, The Institute of Computer Science (FEIT/ICS)Faculty of Electronics and Information Technology (FEIT) Tomasz Gambin (FEIT/ICS) Tomasz Gambin,, The Institute of Computer Science (FEIT/ICS)Faculty of Electronics and Information Technology (FEIT)
Keywords in Polish
sekwencjonowanie następnej generacji, znajdowanie podobieństw pomiędzy sekwencjami DNA, obliczenia równoległe, BBMap, C++
Keywords in English
next generation sequencing, finding similarities between DNA reads, parallel counting, BBMap, C++
Abstract in Polish
Praca opisuje algorytm do korekcji odczytów z sekwenatorów trzeciej generacji. Odczyty takie pokazują sekwencje fragmentów nici DNA i charakteryzują się znaczną stopą błędów (ok. 20% symboli jest błędnych). Dostarczona aplikacja, o nazwie „DNAcorr” zapewnia następujące moduły: — znajdowanie podobieństw pomiędzy sekwencjami DNA; — korekcję sekwencji DNA z wysoką stopą błędu. Dla pierwszego z nich poprzez dostosowanie parametrów algorytmu można osiągnąć wyniki zbliżone do najbardziej uznanych algorytmów rozwiązujących ten problem. Może on być stosowany dla sekwencji pochodzących z sekwenatorów drugiej i trzeciej generacji. Drugi pozwala na poprawę jakości odczytów o dużej ilości błędów poprzez: znalezienie podobieństw ze zbiorem sekwencji DNA o niskiej stopie błędów wykorzystując pierwszy moduł i ustalenie konsensusu. Algorytm znajdowania podobieństw wykorzystuje efektywne struktury danych przechowujące informacje o odczytach. Aplikacja posiada prosty interfejs wykorzystujący linię poleceń. Została ona zaimplemen przy użyciu języka C++ wraz z bibliotekami Boost. „DNAcorr” wykorzystuje wątki co w znaczący sposób redukuje czas obliczeń dla obu modułów. Program został przetestowany dla danych symulowanych.
File
  • File: 1
    Projekt_i_implementacja_algorytmu_do_korekcji_odczytów_z_sekwenatorów_trzeciej_generacji.pdf
Request a WCAG compliant version
Local fields
Identyfikator pracy APD: 35069

Uniform Resource Identifier
https://repo.pw.edu.pl/info/bachelor/WUT00ddd95788e246449b4010151cbb9658/
URN
urn:pw-repo:WUT00ddd95788e246449b4010151cbb9658

Confirmation
Are you sure?
Report incorrect data on this page