Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: DNA sequence assembly

Sortuj według:

Ogranicz wyniki do:

DNA sequence assembly involving an acyclic graph model

Blazewicz J., Frohmberg W., Gawron P., Kasprzak M., Kierzynka M., Swiercz A, Wojciechowski P.

Foundations of Computing and Decision Sciences

2013

Vol. 38, No. 1

25--34

The problem of DNA sequence assembly is well known for its high complexity. Experimental errors of different kinds present in data and huge sizes of the problem instances make this problem very hard to solve. In order to deal with such data, advanced efficient heuristics must be constructed. Here, we propose a new approach to the sequence assembly problem, modeled as the problem of searching for paths in an acyclic digraph. Since the graph representing an assembly instance is not acyclic in general, it is heuristically transformed into the acyclic form. This approach reduces the time of computations significantly and allows to maintain high quality of produced solutions.

Graph reduction and its application to DNA sequence assembly

Błażewicz J., Kasprzak M.

Bulletin of the Polish Academy of Sciences. Technical Sciences

2008

Vol. 56, nr 1

65-70

The results presented here are twofold. First, a heuristic algorithm is proposed which, through removing some unnecessary arcs from a digraph, tends to reduce it into an ad joint and thus simplifies the search for a Hamiltonian cycle. Second, a heuristic algorithm for DNA sequence assembly is proposed, which uses a graph model of the problem instance, and incorporates two independent procedures of reducing the set of arcs - one of them being the former algorithm. Finally, results of tests of the assembly algorithm on parts of chromosome arm 2R of Drosophila melanogaster are presented.