Name
Title | ||
|---|---|---|
An improved problem aware local search algorithm for the DNA fragment assembly problem |
Abstract | ||
|---|---|---|
DNA fragment assembly is a critical and essential early task in a genome project. This task leads to an NP-hard combinatorial optimization problem, and thus, efficient approximate algorithms are required to tackle large problem instances. The Problem Aware Local Search (PALS) is one of the most efficient heuristics for this problem in the literature. PALS gives fairly good solutions but the probability of premature convergence to local optima is significant. In this paper, we propose two modifications to the PALS heuristic in order to ameliorate its performance. The first modification enables the algorithm to improve the tentative solutions in a more appropriate and beneficial way. The second modification permits a significant reduction in the computational demands of the algorithm without significant accuracy loss. Computational experiments confirm that our proposals lead to a more efficient and robust assembler, improving both accuracy and efficiency. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1007/s00500-015-1875-2 | Soft Computing - A Fusion of Foundations, Methodologies and Applications |
Keywords | Field | DocType |
Combinatorial optimization, DNA fragment assembly, Problem Aware Local Search | Mathematical optimization,Heuristic,Computational problem,Premature convergence,Local optimum,Computer science,Combinatorial optimization,Theoretical computer science,Heuristics,Local search (optimization),Optimization problem | Journal |
Volume | Issue | ISSN |
21 | 7 | 1432-7643 |
Citations | PageRank | References |
2 | 0.38 | 13 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| abdelkamel ben ali | 1 | 2 | 0.38 |
| gabriel luque | 2 | 72 | 7.91 |
| Alba Enrique | 3 | 143 | 8.74 |
| Kamal E. Melkemi | 4 | 37 | 3.59 |