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.

JO - Bulletin of the Polish Academy of Sciences: Technical Sciences L1 - http://www.czasopisma.pan.pl/Content/110727/PDF/%2856-1%2965.pdf L2 - http://www.czasopisma.pan.pl/Content/110727 IS - No 1 EP - 70 KW - directed graphs KW - adjoints KW - Hamiltonian cycle KW - reduction of arcs KW - DNA sequence assembly KW - heuristics ER - A1 - Błazewicz, J. A1 - Kasprzak, M. VL - vol. 56 JF - Bulletin of the Polish Academy of Sciences: Technical Sciences SP - 65 T1 - Graph reduction and its application to DNA sequence assembly UR - http://www.czasopisma.pan.pl/dlibra/docmetadata?id=110727