A multilevel ant colony optimization algorithm for classical and isothermic DNA sequencing by hybridization with multiplicity information available
Affiliation:
1. Institute of Computing Science, Poznan University of Technology, Piotrowo 2, 60-965 Poznan, Poland;2. Institute of Bioorganic Chemistry, Polish Academy of Sciences, Noskowskiego 12/14, 61-704 Poznan, Poland;1. INSERM CIC 1432, Plateforme d’Investigation Technologique, Dijon University Hospital, Dijon, France;2. INSERM U1093, Cognition, Action et Plasticité Sensorimotrice, F-21078 Dijon, France;3. LEAD, CNRS UMR 5022, France;4. Rheumatology Department, Dijon University Hospital, Dijon, France;5. Université de Bourgogne, Campus Universitaire, BP 27877, F-21078 Dijon, France;1. Quantum and Molecular Engineering Laboratory, Department of Chemical Engineering, Indian Institute of Technology Kharagpur, Kharagpur 721302, India;2. Centre for Theoretical Studies, Indian Institute of Technology Kharagpur, Kharagpur 721302, India;1. Institute of Development, Southwestern University of Finance and Economics, Chengdu, Sichuan 611130, PR China;2. Department of Emergency Management, Jacksonville State University, AL, USA;3. Department of Energy Economics, School of Economics, Renmin University of China, Beijing 100872, China;4. Department of Economics, School of Economics, Sichuan University, Chengdu, Sichuan 610065, PR China;1. School of Natural Sciences, Bangor University, Bangor LL57 2UW, UK;2. NRM Laboratories, Bracknell, Berkshire, UK;3. Interdisciplinary Research Centre for Agriculture Green Development in Yangtze River Basin, Southwest University, Chongqing, China;4. UWA School of Agriculture and Environment, The University of Western Australia, Perth, WA 6009, Australia
Abstract:
The classical sequencing by hybridization takes into account a binary information about sequence composition. A given element from an oligonucleotide library is or is not a part of the target sequence. However, the DNA chip technology has been developed and it enables to receive a partial information about multiplicity of each oligonucleotide the analyzed sequence consist of. Currently, it is not possible to assess the exact data of such type but even partial information should be very useful.Two realistic multiplicity information models are taken into consideration in this paper. The first one, called “one and many” assumes that it is possible to obtain information if a given oligonucleotide occurs in a reconstructed sequence once or more than once. According to the second model, called “one, two and many”, one is able to receive from biochemical experiment information if a given oligonucleotide is present in an analyzed sequence once, twice or at least three times.An ant colony optimization algorithm has been implemented to verify the above models and to compare with existing algorithms for sequencing by hybridization which utilize the additional information. The proposed algorithm solves the problem with any kind of hybridization errors. Computational experiment results confirm that using even the partial information about multiplicity leads to increased quality of reconstructed sequences. Moreover, they also show that the more precise model enables to obtain better solutions and the ant colony optimization algorithm outperforms the existing ones.Test data sets and the proposed ant colony optimization algorithm are available on: http://bioserver.cs.put.poznan.pl/download/ACO4mSBH.zip.
