TY - JOUR
N2 - 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.
L1 - http://www.czasopisma.pan.pl/Content/110727/PDF/(56-1)65.pdf
L2 - http://www.czasopisma.pan.pl/Content/110727
PY - 2008
IS - No 1
EP - 70
KW - directed graphs
KW - adjoints
KW - Hamiltonian cycle
KW - reduction of arcs
KW - DNA sequence assembly
KW - heuristics
A1 - Błazewicz, J.
A1 - Kasprzak, M.
VL - vol. 56
DA - 2008
T1 - Graph reduction and its application to DNA sequence assembly
SP - 65
UR - http://www.czasopisma.pan.pl/dlibra/publication/edition/110727
T2 - Bulletin of the Polish Academy of Sciences Technical Sciences
ER -