Abstract
Reinforcement learning (RL) aims to build intelligent agents able to optimally act after the training process to solve a given goal task in an autonomous and non-deterministic fashion. It has been successfully employed in several areas; however, few RL-based approaches related to genome assembly have been found, especially when considering real input datasets. De novo genome assembly is a crucial step in a number of genome projects, but due to its high complexity, the outcome of state-of-art assemblers is still insufficient to assist researchers in answering all their scientific questions properly. Hence, the development of better assembler is desirable and perhaps necessary, and preliminary studies suggest that RL has the potential to solve this computational task. In this sense, this paper presents an empirical analysis to evaluate this hypothesis, particularly in higher scale, through performance assessment along with time and space complexity analysis of a theoretical approach to the problem of assembly proposed by [2] using the RL algorithm Q-learning. Our analysis shows that, although space and time complexities are limiting scale issues, RL is shown as a viable alternative for solving the DNA fragment assembly problem.
This study was financed in part by the Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - Brasil (Capes).
Finance Codes: 88882.460068/2019-01 and 88882.445004/2019-01.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
- 2.
All experiments were carried out on a cluster with an Intel(R) Xeon(R) CPU E5-4650 v3 at 2.10 GHz, with 384 Cores and 2 TB of RAM.
- 3.
Supplementary file 2 presents the training times of each experiment.
- 4.
Supplementary file 1 presents an example for better understanding such situation.
References
Bellman, R.E., Dreyfus, S.E.: Applied Dynamic Programming, vol. 2050. Princeton University Press, Princeton (2015)
Bocicor, M.I., Czibula, G., Czibula, I.G.: A reinforcement learning approach for solving the fragment assembly problem. In: 2011 13th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing. IEEE, September 2011
Heather, J.M., Chain, B.: The sequence of sequencers: the history of sequencing DNA. Genomics 107(1), 1–8 (2016)
Li, Z., et al.: Comparison of the two major classes of assembly algorithms: overlap-layout-consensus and de-bruijn-graph. Briefings Funct. Genomics 11(1), 25–37 (2011)
Miller, F.P., Vandome, A.F., McBrewster, J.: Levenshtein Distance: Information Theory, Computer Science, String (Computer Science), String Metric, Damerau? Levenshtein Distance, Spell Checker, Hamming Distance. Alpha Press (2009)
Mnih, V., et al.: Playing Atari with deep reinforcement learning. arXiv preprint arXiv:1312.5602 (2013)
Mnih, V., et al.: Human-level control through deep reinforcement learning. Nature 518(7540), 529–533 (2015)
Pop, M.: Genome assembly reborn: recent computational challenges. Briefings Bioinform. 10(4), 354–366 (2009)
Rangwala, H., Charuvaka, A., Rasheed, Z.: Machine learning approaches for metagenomics. In: Calders, T., Esposito, F., Hüllermeier, E., Meo, R. (eds.) ECML PKDD 2014. LNCS (LNAI), vol. 8726, pp. 512–515. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-44845-8_47
Shang, J., Zhu, F., Vongsangnak, W., Tang, Y., Zhang, W., Shen, B.: Evaluation and comparison of multiple aligners for next-generation sequencing data analysis. BioMed Res. Int. 2014, 1–16 (2014)
Smith, T., Waterman, M.: Identification of common molecular subsequences. J. Mol. Biol. 147(1), 195–197 (1981)
Soueidan, H., Nikolski, M.: Machine learning for metagenomics: methods and tools. arXiv preprint arXiv:1510.06621 (2015)
de Souza, K.P., et al.: Machine learning meets genome assembly. Briefings Bioinform. 20(6), 2116–2129 (2018)
Sutton, R.S., Barto, A.G.: Reinforcement Learning: An Introduction. MIT Press, Cambridge (2018)
Watkins, C.J.C.H.: Learning from delayed rewards (1989)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Xavier, R., de Souza, K.P., Chateau, A., Alves, R. (2020). Genome Assembly Using Reinforcement Learning. In: Kowada, L., de Oliveira, D. (eds) Advances in Bioinformatics and Computational Biology. BSB 2019. Lecture Notes in Computer Science(), vol 11347. Springer, Cham. https://doi.org/10.1007/978-3-030-46417-2_2
Download citation
DOI: https://doi.org/10.1007/978-3-030-46417-2_2
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-46416-5
Online ISBN: 978-3-030-46417-2
eBook Packages: Computer ScienceComputer Science (R0)