# Selection of test instances for string algorithms

Eric Rivals

► To cite this version:

Eric Rivals. Selection of test instances for string algorithms. JOBIM 2025 - Journées Ouvertes en Biologie, Informatique et Mathématiques, Université de Bordeaux; Société Française de BioInformatique (SFBI), Jul 2025, Bordeaux & online, France. lirmm-05234210

HAL Id: lirmm-05234210

https://hal-lirmm.ccsd.cnrs.fr/lirmm-05234210v1

Submitted on 1 Sep 2025

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
# Selection of test instances for string algorithms

Eric Rivals - LIRMM, CNRS, Univ. Montpellier, France

July 9th, 2025

<figure><img src="image_2.png" /></figure>

Keynote talk at JOBIM Conference, Bordeaux, 8-12 July 2025

## Abstract

The consumption of resources, such as electricity and materials used in the manufacture of computers, is increasing sharply with the development of the digital economy and human activities. The question is how to limit this consumption without reducing activities that may be socially useful or necessary.

In bioinformatics, we develop a lot of software, and sometimes many software for the same task, the same computational question. Think, for instance, about genome assembly or read mapping.

When it comes to software development, it's advisable to develop the most comprehensive series of tests to ensure the validity of a piece of software. In the development cycle, we iterate, frequently or automatically, the execution of tests in order to verify the software's correctness at each step. Tests may also be run to evaluate computational speed. This raises scientific questions about the usefulness or redundancy of certain test instances.

Let's take the case of a program that searches for a word in a text, such as your favorite genome. To test the program in all situations, we can run tests on all words of length *k*, for *k* equals 2, then 3, then 4, ..., up to, say 31 (The value *k=31* is common for some DNA sequence analyses). But clearly the number of instances increases exponentially with length *k*, and quickly becomes prohibitive. From the point of view of computer science, we can rephrase our initial question as follows: Can we identify redundant test instances? Can we generate only useful test instances?

I will address these questions during this talk, illustrating them with two complex sequence processing algorithms and showing the impact of instance selection. This principle of test organization is called Equivalence Class Partitioning (ECP) in the domain of software development. The study of these equivalence classes for a given algorithm can be complex. Given the frequency with which tests are run during software development, and the number of software in bioinformatics, this type of approach can help reducing the ecological impact of our developments.

In addition to the advantage in terms of resource usage, the partitioning approach can also inform us about the average program execution time on a class of instances of a given size. This generic approach points to avenues of research for many core algorithms, avenues that may foster interactions with other areas of computer science.

Contact: eric.rivals@lirmm.fr - https://www.lirmm.fr/~rivals