engleski

Protein Database Search Using Partial Order Alignment

Database search is one of the fundamental problems in bioinformatics for which various exact and heuristic methods have been developed. Although execution time for heuristic tools is less several orders of magnitude as compared with well known and used tool BLAST, no tool today is comparable as BLAST regarding sensitivity. The goal of this thesis is to implement the new exact method for local alignment of proteins based on partial order alignment (POA). In ideal case, implemented method should have comparable execution time as BLAST. The main approach for this method is to group proteins from the query with the ones in protein database in order to reduce space of search, i.e. alignment of each query protein with the ones in database. Groups in this sense are partially ordered graphs which contain similar proteins. Once the best graphs with alignments are determined, from those graphs specific alignments will be extracted.

Protein, Database search, Partial order alignment graph, Tight, Loose, Cluster- ing, MSA

nije evidentirano