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 is presented. The algorithm has been tested in computational experiment and compared with an existing tabu search method for the same problem. The results clearly show that the genetic algorithm outperformed the tabu search approach.
Mots-clés : peptide sequencing, combinatorial optimization problem, genetic algorithm, tabu search algorithm
@article{RO_2010__44_2_153_0,
author = {B{\l}a\.zewicz, Jacek and Borowski, Marcin and Formanowicz, Piotr and G{\l}owacki, Tomasz},
title = {Genetic and {Tabu} search algorithms for peptide assembly problem},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {153--166},
publisher = {EDP-Sciences},
volume = {44},
number = {2},
year = {2010},
doi = {10.1051/ro/2010012},
zbl = {1187.92036},
language = {en},
url = {http://archive.numdam.org/articles/10.1051/ro/2010012/}
}
TY - JOUR AU - Błażewicz, Jacek AU - Borowski, Marcin AU - Formanowicz, Piotr AU - Głowacki, Tomasz TI - Genetic and Tabu search algorithms for peptide assembly problem JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2010 SP - 153 EP - 166 VL - 44 IS - 2 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ro/2010012/ DO - 10.1051/ro/2010012 LA - en ID - RO_2010__44_2_153_0 ER -
%0 Journal Article %A Błażewicz, Jacek %A Borowski, Marcin %A Formanowicz, Piotr %A Głowacki, Tomasz %T Genetic and Tabu search algorithms for peptide assembly problem %J RAIRO - Operations Research - Recherche Opérationnelle %D 2010 %P 153-166 %V 44 %N 2 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ro/2010012/ %R 10.1051/ro/2010012 %G en %F RO_2010__44_2_153_0
Błażewicz, Jacek; Borowski, Marcin; Formanowicz, Piotr; Głowacki, Tomasz. Genetic and Tabu search algorithms for peptide assembly problem. RAIRO - Operations Research - Recherche Opérationnelle, Tome 44 (2010) no. 2, pp. 153-166. doi : 10.1051/ro/2010012. http://archive.numdam.org/articles/10.1051/ro/2010012/
[1] , , and , On graph theoretical models for peptide sequence assembly. Foundations of Computing and Decision Sciences 30 (2005) 183-191. | Zbl
[2] , , and , Tabu Search Method for Determining Sequences of Amino Acids in Long Polypeptides. Lect. Notes Comput. Sci. 3449 (2005) 22-32.
[3] and , Combinatorial optimization in DNA mapping - a computational thread of the Simplified Partial Digest Problem. RAIRO - Oper. Res. 39 (2005) 227-241. | Zbl
[4] , and , Selected combinatorial problems of computational biology. Eur. J. Oper. Res. 161 (2005) 585-597. | Zbl
[5] , Selected Combinatorial Aspects of Biological Sequence Analysis, Poznań, Publishing House of Poznań University of Technology (2005).
[6] , The complexity of the overlap method for sequencing biopolymers, J. Theo. Biol. 101 (1983) 1-17.
[7] , Tabu Search, Part I. ORSA Journal on Computing 1 (1989) 190-206. | Zbl
[8] , Tabu Search, Part II. ORSA Journal on Computing 1 (1990) 4-32. | Zbl
[9] and , A general method applicable to the search for similarities in the amino acid sequence of two proteins. J. Mol. Biol. 48 (1970) 443-453.
[10] , Comput. molecular biology. An algorithmic approach. Cambridge, Massachusetts, The MIT Press (2000). | Zbl
[11] and , Introduction to computational molecular biology. Boston, PWS Publishing Co. (1996).
[12] , Biochemistry, 4th edition. New York, W.H. Freeman and Company (1995).
[13] , Introduction to computational biology, London, Chapman & Hall (1995). | Zbl
Cité par Sources :
