J. Blazewicz, M. Kasprzak,
"Graph reduction and its application to DNA sequence assembly",
Bulletin of the Polish Academy of Sciences. Technical Sciences 56 (2008) 65-70.
Download full text
Abstract:
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 adjoint 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.
Back to the List of publications
5 Jun 2008