J. Blazewicz, W. Frohmberg, P. Gawron, M. Kasprzak, M. Kierzynka,
A. Swiercz, P. Wojciechowski
"DNA sequence assembly involving an acyclic graph model"
Foundations of Computing and Decision Sciences 38 (2013) 25-34.
Download full text
Abstract:
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.
Back to the List of publications
26 Feb 2013