Maria-Iuliana BOCICOR, Gabriela CZIBULA, István Gergely CZIBULA
Babeş-Bolyai University,
1, M. Kogălniceanu street, Cluj-Napoca, 400084, Romania

Abstract: The process of DNA sequencing has nowadays become of great importance in basic biology research, as well as in various fields such as medicine, biotechnology or forensic biology. The fragment assembly problem is a very complex optimization problem that deals with sequencing of DNA, and many computational techniques including computational intelligence algorithms were designed for finding good solutions for this problem. Since DNA fragment assembly is a crucial part of any sequencing project, researchers are still focusing on developing better assemblers. We are introducing in this paper a distributed reinforcement learning based approach for solving the fragment assembly problem, an NP-complete optimization problem that attempts to reconstruct the original DNA sequence from a large number of fragments, each several hundred base-pairs long. Our model is based on a distributed Q-learning approach. The experimental evaluation of the proposed system has provided encouraging results, indicating the potential of our proposal. The advantages and drawbacks of the proposed approach are also emphasized.

Keywords: Bioinformatics, distributed reinforcement learning, DNA fragment assembly.

>>Full text
CITE THIS PAPER AS:
Maria-Iuliana BOCICOR, Gabriela CZIBULA, István Gergely CZIBULA, A Distributed Q-Learning Approach to Fragment Assembly, Studies in Informatics and Control, ISSN 1220-1766, vol. 20 (3), pp. 221-232, 2011. https://doi.org/10.24846/v20i3y201103

1. Introduction

The process of DNA sequencing has nowadays become of great importance in basic biology research, as well as in various fields such as medicine, biotechnology or forensic biology. Several techniques have been developed to achieve the DNA sequencing, but the main problem with the current technology is that it cannot read an entire genome at once, not even more than 1000 bases.

The DNA fragment assembly (FA) is a technique that attempts to reconstruct the original DNA sequence from a large number of fragments, each several hundred base-pairs long [1]. It is an NP-hard combinatorial optimization problem [2] which is growing in importance and complexity as more research centers become involved on sequencing new genomes [3]. Various heuristics, including computational intelligence algorithms, have been designed for solving the fragment assembly problem, but since this problem is a crucial part of any sequencing project, better assemblers are needed [3].

In this paper we aim at proposing a distributed reinforcement learning based model for solving the DNA Fragment Assemby problem. Reinforcement Learning (RL) [4] is an approach to machine intelligence in which an agent [5] can learn to behave in a certain way by receiving punishments or rewards on its chosen actions.

The model proposed in this paper extends toward a distributed approach the reinforcement learning based model that we have previously introduced in [6] for solving the FA problem. To our knowledge, except for the ant [7] based approaches, the DNA Fragment Assembly problem has not been addressed in the literature using distributed reinforcement learning, so far.

The rest of the paper is organized as follows. Section 2 presents the DNA fragment assembly problem and Section 3 briefly describes existing approaches in solving the considered problem. The fundamentals of distributed reinforcement learning are given in Section 4. Section 5 introduces the distributed reinforcement learning model that we propose for solving the fragment assembly problem. An experimental evaluation of the proposed approach is given in Section 6, and Section 7 provides an analysis of the introduced distributed model, emphasizing its advantages and drawbacks. Section 8 contains some conclusions of the paper and future development of our work.

REFERENCES

1. LI, L., S. KHURI, A Comparison of DNA Fragment Assembly Algorithms, in Proc. of the Intl. Conf. on Mathematics and Engineering Techniques in Medicine and Biological Sciences. CSREA Press, 2004, pp. 329-335.
2. TALMACIU, M., E. NECHITA, Some Combinatorial Optimization Problems for Weak-bisplit Graphs, Studies in Informatics and Control, vol. 19, no. 4, 2010, pp. 427-434.