Displaying similar documents to “Combinatorial optimization in DNA mapping — A computational thread of the simplified partial digest problem”

Genetic and Tabu search algorithms for peptide assembly problem

Jacek Błażewicz, Marcin Borowski, Piotr Formanowicz, Tomasz Głowacki (2010)

RAIRO - Operations Research

Similarity:

Determining amino acid sequences of protein molecules is one of the most important issues in molecular biology. These sequences determine protein structure and functionality. Unfortunately, direct biochemical methods for reading amino acid sequences can be used for reading short sequences only. This is the reason, which makes peptide assembly algorithms an important complement of these methods. In this paper, a genetic algorithm solving the problem of short amino acid sequence assembly...

Experiments with variants of ant algorithms.

Thomas Stützle, Sebastian Linke (2002)

Mathware and Soft Computing

Similarity:

A number of extensions of Ant System, the first ant colony optimization (ACO) algorithm, were proposed in the literature. These extensions typically achieve much improved computational results when compared to the original Ant System. However, many design choices of Ant System are left untouched including the fact that solutions are constructed, that real-numbers are used to simulate pheromone trails, and that explicit pheromone evaporation is used. In this article we experimentally...

A new practical linear space algorithm for the longest common subsequence problem

Heiko Goeman, Michael Clausen (2002)

Kybernetika

Similarity:

This paper deals with a new practical method for solving the longest common subsequence (LCS) problem. Given two strings of lengths m and n , n ≥ m , on an alphabet of size s , we first present an algorithm which determines the length p of an LCS in O ( n s + min { m p , p ( n - p ) } ) time and O ( n s ) space. This result has been achieved before [ric94,ric95], but our algorithm is significantly faster than previous methods. We also provide a second algorithm which generates an LCS in O ( n s + min { m p , m log m + p ( n - p ) } ) time while preserving the linear space bound,...

Combining constraint Propagation and meta-heuristics for searching a Maximum Weight Hamiltonian Chain

Yves Caseau (2006)

RAIRO - Operations Research

Similarity:

This paper presents the approach that we developed to solve the ROADEF 2003 challenge problem. This work is part of a research program whose aim is to study the benefits and the computer-aided generation of hybrid solutions that mix constraint programming and meta-heuristics, such as large neighborhood search (LNS). This paper focuses on three contributions that were obtained during this project: an improved method for propagating Hamiltonian chain constraints, a fresh look at...

An introduction to multiprocessor scheduling.

J.K. Lenstra, A.H.G. Rinnooy (1981)

Qüestiió

Similarity:

This is a tutorial survey of recent results in the area of multiprocessor scheduling. Computational complexity theory provides the framework in which these results are presented. They involve on one hand the development of new polynomial optimization algorithms, and on the other hand the application of the concept of NP-hardness as well as the analysis of approximation algorithms.

A sparse dynamic programming algorithm for alignment with non-overlapping inversions

Alair Pereira Do Lago, Ilya Muchnik, Casimir Kulikowski (2005)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

Alignment of sequences is widely used for biological sequence comparisons, and only biological events like mutations, insertions and deletions are considered. Other biological events like inversions are not automatically detected by the usual alignment algorithms, thus some alternative approaches have been tried in order to include inversions or other kinds of rearrangements. Despite many important results in the last decade, the complexity of the problem of alignment with inversions...

Towards a theory of practice in metaheuristics design: A machine learning perspective

Mauro Birattari, Mark Zlochin, Marco Dorigo (2006)

RAIRO - Theoretical Informatics and Applications

Similarity:

A number of methodological papers published during the last years testify that a need for a thorough revision of the research methodology is felt by the operations research community – see, for example, [Barr (1995) 9–32; Eiben and Jelasity, 582–587; Hooker, (1995) 33–42; Rardin and Uzsoy, (2001) 261–304]. In particular, the performance evaluation of nondeterministic methods, including widely studied metaheuristics such as evolutionary...