No Access

Department of Applied Biology, University of Frères Mentouri Constantine 1, Constantine 25000, Algeria

Corresponding author.

Search for more papers by this author

Billel Kenidra

Ecole Nationale Suprieure dInformatique (ESI), BP 68M Oued-Smar, Alger 16270, Algeria

E-mail Address: b_kenidra@esi.dz

Search for more papers by this author

Hamza Bouanaka

Department of Applied Biology, University of Frères Mentouri Constantine 1, Constantine 25000, Algeria

E-mail Address: hamza.bouanaka@umc.edu.dz

Search for more papers by this author

, and

Salim Chikhi

MISC Laboratory, University of Abdelhamid Mehri Constantine 2, Constantine 25000, Algeria

E-mail Address: salim.chikhi@univ-constantine2.dz

Search for more papers by this author

https://doi.org/10.1142/S1469026823500220Cited by:0 (Source: Crossref)

Abstract

With the appearance of complete mammalian genomes, comparative approaches have experienced a recent upsurge. Searching maximal exact match is among the most used tasks in sequence searching within a larger DNA sequence or database. Many exact algorithms have been designed to deal with this problem. The best improvements made by these algorithms have led to a time and space complexity of O(n) and they remain practically less effective for large sequences. Heuristic methods will therefore be a good alternative to implement. In this work, we present an efficient heuristic algorithm based on PSO metaheuristic to deal with the problem of searching the maximal exact match of small searched sequences in large ones. The time and space complexity of the designed algorithm is of O(1). The experimental results showed the efficiency of the proposed search algorithm for finding maximal exact match in large sequences when compared with two other sequence searching algorithms.

Keywords:

Remember to check out the Most Cited Articles!
Check out these titles in artificial intelligence!

References

1. J. Garza-Ulloa , Chapter 1—biomedical engineering and the evolution of artificial intelligence, in Applied Biomedical Engineering Using Artificial Intelligence and Cognitive Models, ed. J. Garza-Ulloa (Academic Press, 2022), pp. 1–37. Google Scholar
2. A. Srikantha, A. S. Bopardikar, K. K. Kaipa, P. Venkataraman, K. Lee, T. Ahn and R. Narayanan , A fast algorithm for exact sequence search in biological sequences using polyphase decomposition, Bioinformatics 26(18) (2010) i414–i419. Crossref, Google Scholar
3. A. Amir, P. Charalampopoulos, S. P. Pissis and J. Radoszewski , Dynamic and internal longest common substring, Algorithmica 82(12) (2020) 3707–3743. Crossref, Google Scholar
4. R. Bellman , The theory of dynamic programming, Bull. Am. Math. Soc. 60(6) (1954) 503–515. Crossref, Google Scholar
5. Z. Zhi and S. Fushan, Lecture 4: Suffix tree and suffix array, September 17, 2007. Google Scholar
6. P. Weiner , Linear pattern matching algorithms, in 14th Annual Symp. Switching and Automata Theory (swat 1973) (IEEE, 1973), pp. 1–11. Crossref, Google Scholar
7. E. Ukkonen , On-line construction of suffix trees, Algorithmica 14(3) (1995) 249–260. Crossref, Google Scholar
8. U. Manber and G. Myers , Suffix arrays: A new method for on-line string searches, SIAM J. Comput. 22(5) (1993) 935–948. Crossref, Google Scholar
9. Z. Khan, J. S. Bloom, L. Kruglyak and M. Singh , A practical algorithm for finding maximal exact matches in large sequence datasets using sparse suffix arrays, Bioinformatics 25(13) (2009) 1609–1616. Crossref, Google Scholar
10. P. Charalampopoulos, T. Kociumaka, S. P. Pissis and J. Radoszewski, Faster algorithms for longest common substring, preprint, arXiv:2105.03106, 2021. Google Scholar
11. A. Amir and I. Boneh , Locally maximal common factors as a tool for efficient dynamic string algorithms, in Annual Symp. Combinatorial Pattern Matching (CPM 2018) (Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018). Google Scholar
12. A. Amir, P. Charalampopoulos, S. P. Pissis and J. Radoszewski , Dynamic and internal longest common substring, Algorithmica 82(12) (2020) 3707–3743. Crossref, Google Scholar
13. P. Charalampopoulos, P. Gawrychowski and K. Pokorski, Dynamic longest common substring in polylogarithmic time, preprint, arXiv:2006.02408, 2020. Google Scholar
14. S. Ben-Nun, S. Golan, T. Kociumaka and M. Kraus, Time-space tradeoffs for finding a long common substring, preprint, arXiv:2003.02016, 2020. Google Scholar
15. T. Kociumaka, T. Starikovskaya and H. W. Vildhøj , Sublinear space algorithms for the longest common substring problem, in European Symp. Algorithms (Springer, 2014), pp. 605–617. Crossref, Google Scholar
16. T. Starikovskaya and H. W. Vildhøj , Time-space trade-offs for the longest common substring problem, in Annual Symp. Combinatorial Pattern Matching (Springer, 2013), pp. 223–234. Crossref, Google Scholar
17. X. Li and M. Clerc , Swarm intelligence, in Handbook of Metaheuristics (Springer, 2019), pp. 353–384. Crossref, Google Scholar
18. Search longest common substrings using generalized suffix trees built with ukkonen’s algorithm, written in python 2.7, https://gist.github.com/Oe2tam/f39e5525cf328a623ea4917fe05ce474. Google Scholar
19. Longest common substring (space optimized dp solution), https://www.geeksforgeeks.org/longest-common-substring-space-optimized-dp-solution/ (April 2021). Google Scholar
20. Human genome resources at ncbi—ncbi, https://www.ncbi.nlm.nih.gov/genome/guide/human/. Google Scholar