Exploring Reinforcement Learning Methods for Multiple Sequence Alignment: A Brief Review

Open Access

Issue		BIO Web Conf. Volume 75, 2023 The 5^th International Conference on Bioinformatics, Biotechnology, and Biomedical Engineering (BioMIC 2023)


Article Number		01004
Number of page(s)		7
Section		Bioinformatics and Data Mining
DOI		https://doi.org/10.1051/bioconf/20237501004
Published online		15 November 2023

M. Chatzou, C. Magis, J. M. Chang, C. Kamena, G. Bussotti, I. Erb, C. Notredame, ‘Multiple sequence alignment modeling: methods and applications’, Briefings in Bioinformatics, vol. 17, no. 6, pp. 1009–1023, Nov. 2016, doi: 10.1093/bib/bbv099. [CrossRef] [PubMed] [Google Scholar]
R. V. Noorden, B. Maher, and R. Nuzzo, ‘Nature explores the most-cited research of all time.’ The top 100 papers. Nature 2014;514:550–3. [Google Scholar]
J. D. Thompson, D. G. Higgins, and T. J. Gibson, ‘CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice’, Nucleic Acids Res 1994;22:4673–90. [CrossRef] [PubMed] [Google Scholar]
S. R. Eddy, ‘A Probabilistic Model of Local Sequence Alignment That Simplifies Statistical Significance Estimation’, PLoS Computational Biology, vol. 4, no. 5, p. e1000069, May 2008, doi: 10.1371/journal.pcbi.1000069. [CrossRef] [PubMed] [Google Scholar]
C. Lee, C. Grasso, and M. F. Sharlow, ‘Multiple sequence alignment using partial order graphs’, Bioinformatics, vol. 18, no. 3, pp. 452–464, Mar. 2002, doi: 10.1093/bioinformatics/18.3.452. [CrossRef] [Google Scholar]
S. B. Needleman and C. D. Wunsch, ‘A general method applicable to the search for similarities in the amino acid sequence of two proteins’, Journal of Molecular Biology, vol. 48, no. 3, pp. 443–453, Mar. 1970, doi: 10.1016/0022-2836(70)90057-4. [CrossRef] [Google Scholar]
T. F. Smith and M. S. Waterman, ‘Identification of common molecular subsequences’, Journal of Molecular Biology, vol. 147, no. 1, pp. 195–197, Mar. 1981, doi: 10.1016/0022-2836(81)90087-5. [CrossRef] [PubMed] [Google Scholar]
P. Hogeweg and B. Hesper, ‘The alignment of sets of sequences and the construction of phyletic trees: An integrated method’, Journal of Molecular Evolution vol. 20, no. 2, pp. 175–186, Jun. 1984, doi: 10.1007/BF02257378. [CrossRef] [PubMed] [Google Scholar]
C. Notredame, D. G. Higgins, and J. Heringa, ‘Tcoffee: a novel method for fast and accurate multiple sequence alignment 1 1Edited by J. Thornton’, Journal of Molecular Biology, vol. 302, no. 1, pp. 205–217, Sep. 2000, doi: 10.1006/jmbi.2000.4042. [CrossRef] [PubMed] [Google Scholar]
C. B. Do, M. S. P. Mahabhashyam, M. Brudno, and S. Batzoglou, ‘ProbCons: Probabilistic consistencybased multiple sequence alignment’, Genome Research, vol. 15, no. 2, pp. 330–340, Feb. 2005, doi: 10.1101/gr.2821705. [CrossRef] [PubMed] [Google Scholar]
I. M. Wallace, O. Orla, and D. G. Higgins, ‘Evaluation of iterative alignment algorithms for multiple alignment’, Bioinformatics, vol. 21, no. 8, pp. 1408–1414, Apr. 2005, doi: 10.1093/bioinformatics/bti159. [CrossRef] [Google Scholar]
K. Katoh, ‘MAFFT: a novel method for rapid multiple sequence alignment based on fast Fourier transform’, Nucleic Acids Research, vol. 30, no. 14, pp. 3059–3066, Jul. 2002, doi: 10.1093/nar/gkf436. [CrossRef] [PubMed] [Google Scholar]
R. C. Edgar, ‘MUSCLE: a multiple sequence alignment method with reduced time and space complexity’, BMC Bioinformatics, vol. 5, no. 1, p. 113, 2004, doi: 10.1186/1471-2105-5-113. [CrossRef] [PubMed] [Google Scholar]
F. Sievers, A. Wilm, D. Dineen, T. J. Gibson, K. Karplus, W. Li, R. Lopez, H. McWilliam, M. Remmert, J. Soding, J. D. Thompson and D. G. Higgins, ‘Fast, scalable generation of high‐quality protein multiple sequence alignments using Clustal Omega’, Molecular Systems Biology, vol. 7, no. 1, p. 539, Jan. 2011, doi: 10.1038/msb.2011.75. [CrossRef] [PubMed] [Google Scholar]
L. Wang and T. Jiang, ‘On the Complexity of Multiple Sequence Alignment’, Journal of Computational Biology, vol. 1, no. 4, pp. 337–348, Jan. 1994, doi: 10.1089/cmb.1994.1.337. [CrossRef] [PubMed] [Google Scholar]
C. Kemena and C. Notredame, ‘Upcoming challenges for multiple sequence alignment methods in the highthroughput era’, Bioinformatics, vol. 25, no. 19, pp. 2455–2465, Oct. 2009, doi: 10.1093/bioinformatics/btp452. [CrossRef] [Google Scholar]
D. J. Lipman, S. F. Altschul, and J. D. Kececioglu, ‘A tool for multiple sequence alignment.’, Proceedings of the National Academy of Sciences. U.S.A., vol. 86, no. 12, pp. 4412–4415, Jun. 1989, doi: 10.1073/pnas.86.12.4412. [CrossRef] [PubMed] [Google Scholar]
J. D. Thompson, P. Koehl, R. Ripp, and O. Poch, ‘BAliBASE 3.0: Latest developments of the multiple sequence alignment benchmark’, Proteins, vol. 61, no. 1, pp. 127–136, Jul. 2005, doi: 10.1002/prot.20527. [CrossRef] [PubMed] [Google Scholar]
R. S. Sutton and A. G. Barto, Reinforcement learning: an introduction, Second edition. in Adaptive computation and machine learning series. Cambridge, Massachusetts: The MIT Press, 2018. [Google Scholar]
J. Clifton and E. Laber, ‘Q-Learning: Theory and Applications’, Annual Review of Statistics and Its Application, vol. 7, no. 1, pp. 279–301, Mar. 2020, doi: 10.1146/annurev-statistics-031219-041220. [CrossRef] [Google Scholar]
R. J. Williams, ‘Simple statistical gradient-following algorithms for connectionist reinforcement learning’, Machine Learning 8(23) [Google Scholar]
V. Mnih, A. P. Badia, M. Mirza, A. Graves, T. Harley, T. P Lillicrap, D. Silver, K. Kavukcuoglu., ‘Asynchronous Methods for Deep Reinforcement Learning’, International Conference on Machine Learning 2016. [Google Scholar]
F.-M. Luo, S. Jiang, Y. Yu, Z. Zhang, and Y.-F. Zhang, ‘Adapt to Environment Sudden Changes by Learning a Context Sensitive Policy’, The Association for the Advancement of Artificial Intelligence, vol. 36, no. 7, pp. 7637–7646, Jun. 2022, doi: 10.1609/aaai.v36i7.20730. [Google Scholar]
R. Bellman, Dynamic programming. Princeton, NJ: Princeton Univ. Pr, 1984. [Google Scholar]
V. Mnih, K. Kavukcuoglu, D. Silver, A. Graves, I. Antonoglou, D. Wierstra, M. Riedmiller., ‘Playing Atari with Deep Reinforcement Learning’, arXiv preprint arXiv:1312.5602, 2013. [Google Scholar]
J. Luketina, N. Nardelli, G. Farquhar, J. Foerster, J. Andreas, E. Grefenstette, S. Whiteson, T. Rocktäschel., ‘A Survey of Reinforcement Learning Informed by Natural Language’. arXiv, Jun. 10, 2019. Accessed: Jul. 25, 2023. Available: http://arxiv.org/abs/1906.03926 [Google Scholar]
I.-G. Mircea, I. Bocicor, and G. Czibula, ‘A Reinforcement Learning Based Approach to Multiple Sequence Alignment’, in Soft Computing Applications, vol. 634, V. E. Balas, L. C. Jain, and M. M. Balas, Eds., in Advances in Intelligent Systems and Computing, vol. 634., Cham: Springer International Publishing, 2018, pp. 54–70. doi: 10.1007/978-3-319-62524-9_6. [Google Scholar]
R. Kinattinkara Ramakrishnan, J. Singh, and M. Blanchette, ‘RLALIGN: A Reinforcement Learning Approach for Multiple Sequence Alignment’, in 2018 IEEE 18th International Conference on Bioinformatics and Bioengineering (BIBE), Taichung, Taiwan: IEEE, Oct. 2018, pp. 61–66. doi: 10.1109/BIBE.2018.00019. [CrossRef] [Google Scholar]
R. Jafari, M. M. Javidi, and M. Kuchaki Rafsanjani, ‘Using deep reinforcement learning approach for solving the multiple sequence alignment problem’, SN Applied Sciences vol. 1, no. 6, p. 592, Jun. 2019, doi: 10.1007/s42452-019-0611-4. [CrossRef] [Google Scholar]
Y. Zhang, Q. Zhang, Y. Liu, M. Lin, and C. Ding, ‘Multiple Sequence Alignment based on deep Q network with negative feedback policy’, Computational Biology and Chemistry, vol. 101, p. 107780, Dec. 2022, doi: 10.1016/j.compbiolchem.2022.107780. [CrossRef] [PubMed] [Google Scholar]
X. Xiang, D. Zhang, J. Qin, and Y. Fu, ‘Ant Colony with Genetic Algorithm Based on Planar Graph for Multiple Sequence Alignment’, Information Technology J., vol. 9, no. 2, pp. 274–281, Feb. 2010, doi: 10.3923/itj.2010.274.281. [CrossRef] [Google Scholar]
H. Carroll, W. Beckstead, T. O’Connor, M. Ebbert, M. Clement, Q. Snell, et D. McClellan., ‘DNA reference alignment benchmarks based on tertiary structure of encoded proteins’, Bioinformatics, vol. 23, no. 19, pp. 2648–2649, Oct. 2007, doi: 10.1093/bioinformatics/btm389. [CrossRef] [Google Scholar]
C. Kanz, ‘The EMBL Nucleotide Sequence Database’, Nucleic Acids Research, vol. 33, no. Database issue, pp. D29–D33, Dec. 2004, doi: 10.1093/nar/gki098. [CrossRef] [Google Scholar]

Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.

Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.

Initial download of the metrics may take a while.