Many computational intelligence approaches have been used for the fragmentassemblyproblem. However, the comparison and analysis of these approaches is difficult due to the lack of availability of standard benchmarks...
详细信息
Many computational intelligence approaches have been used for the fragmentassemblyproblem. However, the comparison and analysis of these approaches is difficult due to the lack of availability of standard benchmarks. Although similar datasets may be used as a starting point, there is not enough information to reproduce the exact overlaps matrix for the fragments used by the various approaches, creating a problem for consistency. This paper presents a collection of benchmark datasets for a wide range of fragment lengths, number of fragments, and sequence lengths, along with a description of the method used to produce them. A website has been created to maintain the datasets and the tables of results at http://***/fragbench/. Researchers are invited to add to the datasets by following the method described, as well as to submit results obtained by their algorithms on the benchmarks.
The dna fragment assembly problem (FAP) is an NP-complete that consists in reconstructing a dna sequence from a set of fragments taken at random. The FAP has been successfully and efficiently solved through metaheuris...
详细信息
The dna fragment assembly problem (FAP) is an NP-complete that consists in reconstructing a dna sequence from a set of fragments taken at random. The FAP has been successfully and efficiently solved through metaheuristics. But these methods usually face difficulties to succeed when noise appears in the input data or during the search, specially in large instances. In this regard, the design of more efficient techniques are indeed necessary. One example of these techniques found in literature is the problem Aware Local Search (PALS) which represents a state-of-the-art and robust assembler to solve noisy instances. Although PALS performs better than other metaheuristics, the quality of the achieved solutions by this method can still be improved. Towards this aim, this work proposes a new hybrid and effective method that combines a local search technique specially designed for this problem (PALS) with Simulated Annealing (SA), which is further distributed following an island model. Our proposed hybrid approach showed an improved performance on the largest non-noisy and noisy instances when compared separately with Simulated Annealing and PALS. (C) 2014 Elsevier Inc. All rights reserved.
Many problems involving dna can be modeled by families of intervals. However, traditional interval graphs do not take into account the repeat structure of a dna molecule. In the simplest case, one repeat with two copi...
详细信息
Many problems involving dna can be modeled by families of intervals. However, traditional interval graphs do not take into account the repeat structure of a dna molecule. In the simplest case, one repeat with two copies, the underlying line can be seen as folded into a loop. We propose a new definition that respects repeats and define loop graphs as the intersection graphs of arcs of a loop. The class of loop graphs contains the class of interval graphs and the class of circular-arc graphs. Every loop graph has interval number 2. We characterize the trees that are loop graphs. The characterization yields a polynomial-time algorithm which given a tree decides whether it is a loop graph and. in the affirmative case. produces it loop representation for the tree. (c) 2006 Elsevier B.V. All rights reserved.
dnafragmentassembly - an NP-Hard problem-is one of the major steps in of dna sequencing. Multiple strategies have been used for this problem, including greedy graph-based algorithms, deBruijn graphs, and the overlap...
详细信息
dnafragmentassembly - an NP-Hard problem-is one of the major steps in of dna sequencing. Multiple strategies have been used for this problem, including greedy graph-based algorithms, deBruijn graphs, and the overlap-layout-consensus approach. This study focuses on the overlap-layout-consensus approach. Heuristics and computational intelligence methods are combined to exploit their respective benefits. These algorithm combinations were able to produce high quality results surpassing the best results obtained by a number of competitive algorithms specially designed and tuned for this problem on thirteen of sixteen popular benchmarks. This work also reinforces the necessity of using multiple search strategies as it is clearly observed that algorithm performance is dependent on problem instance;without a deeper look into many searches, top solutions could be missed entirely. (C) 2016 Published by Elsevier Ireland Ltd.
As more research centers embark on sequencing new genomes, the problem of dnafragmentassembly for shotgun sequencing is growing in importance and complexity. Accurate and fast assembly is a crucial part of any seque...
详细信息
ISBN:
(纸本)0780393635
As more research centers embark on sequencing new genomes, the problem of dnafragmentassembly for shotgun sequencing is growing in importance and complexity. Accurate and fast assembly is a crucial part of any sequencing project and since the dna fragment assembly problem is NP-hard, exact solutions are very difficult to obtain. Various heuristics, including genetic algorithms, were designed for solving the fragmentassemblyproblem. While the sequential genetic algorithm has given good results, it is unable to sequence very large dna molecules. In this work, we present two parallel methods, a distributed genetic algorithm and a parallel simulated annealing, to solve problem instances that are 77K base pairs long accurately.
暂无评论