Short-Term Scientific Mission

Enhancing Search Algorithms for Computational Biology: Advanced Techniques and Applications

Main theme: Problem Modelling and User Experience
Grantee: Marko Djukanović, University of Banja Luka, Faculty of Natural Sciences and Mathematics, Banja Luka, Bosnia and Herzegovina
Host: Christian Blum, Artificial Intelligence Research Institute (IIIA-CSIC), Barcelona, Spain

Start date: 2025-07-04
End date: 2025-07-10
Awarded: 2025-03-07
Report approved: 2025-07-28

Description

This STSM aims to develop advanced search strategies for sequence problems from bioinformatics, with the focus on predicting potential mutations in molecular structures that yield possible genetic abnormalities. Current optimization methods are limited to small problem instances, being hardly applicable for real-world biological instances. To fill this gap, the aim is to develop scalable ILP-based metaheuristic approaches, leveraging advanced optimization techniques like the popular Construct, Merge, Solve, Adapt framework. The expected outcomes include new methodologies capable of handling larger datasets, benchmark implementations, and open-source tools. These advancements will help biologists to improve the understanding of molecular evolution and disease-related mutations.

Achievements

The primary focus of the STSM was on the development of a robust ILP-based hybrid metaheuristic aimed at solving a challenging optimization problem in gene reconstruction. Specifically, a tailored version of the Construct, Merge, Solve, and Adapt (CMSA) was designed to address the real-world Longest Filled Common Subsequence problem. It leverages the strengths of black-box solvers to iteratively solve strategically constructed subinstances.

In addition to achieving state-of-the-art empirical results of the CMSA approach, the STSM also laid the foundation for future collaboration in exploring more advanced CMSA variants that integrate reinforcement or deep learning techniques to further enhance the search process.