<abstract xmlns="http://www.w3.org/1999/xhtml"><p> The problem of DNA sequence assembly is well known for its high complexity. Experimental errors of di erent 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. </p></abstract>

The problem of DNA sequence assembly is well known for its high complexity. Experimental errors of di erent 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.

Dna Sequence Assembly Involving an Acyclic Graph Model

Institute of Computing Science, Poznan University of Technology, Piotrowo 2, 60-965 Poznan, Poland

Institute of Bioorganic Chemistry, Polish Academy of Sciences, Poznan, Poland

Luxembourg Centre for Systems Biomedicine, University of Luxembourg

Foundations of Computing and Decision Sciences

{"article-title":"Dna Sequence Assembly Involving an Acyclic Graph Model"}

The problem of DNA sequence assembly is well known for its high complexity. Experimental errors of di erent kinds present in data and huge sizes of the problem...

Dna Sequence Assembly Involving an Acyclic Graph Model

Published Online: Feb 23, 2013

Page range: 25 - 34

DOI: https://doi.org/10.2478/v10209-011-0019-4

Keywords
DNA sequence assembly, acyclic graph model, GPU programming

This content is open access.

Dna Sequence Assembly Involving an Acyclic Graph Model

Published Online: Feb 23, 2013

Page range: 25 - 34

DOI: https://doi.org/10.2478/v10209-011-0019-4

KeywordsDNA sequence assembly, acyclic graph model, GPU programming

This content is open access.

Keywords
DNA sequence assembly, acyclic graph model, GPU programming