Evaluation of a Permutation-Based Evolutionary Framework for Lyndon Factorizations

Authors Organisations
Type Conference Proceeding (Non-Journal item)
Original languageEnglish
Title of host publicationParallel Problem Solving from Nature – PPSN XVI
Subtitle of host publication16th International Conference, Leiden, The Netherlands, September 5-9, 2020, Proceedings
EditorsThomas Bäck, Mike Preuss, André Deutz, Hao Wang, Carola Doerr, Michael Emmerich, Heike Trautmann
PublisherSpringer Nature
ISBN (Electronic)9783030581121
ISBN (Print)9783030581114
Publication statusPublished - 31 Aug 2020
EventParallel Problem Solving Nature - Leiden, Netherlands
Duration: 05 Sep 202009 Sep 2020
Conference number: 16

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


ConferenceParallel Problem Solving Nature
Abbreviated titlePPSN
Period05 Sep 202009 Sep 2020
Internet address
Permanent link
Show download statistics
View graph of relations
Citation formats


String factorization is an important tool for partitioning data for parallel processing and other algorithmic techniques often found in the context of big data applications such as bioinformatics or compression. Duval's well-known algorithm uniquely factors a string over an ordered alphabet into Lyndon words, i.e., patterned strings which are strictly smaller than all of their cyclic rotations. While Duval's algorithm produces a pre-determined factorization, modern applications motivate the demand for factorizations with specific properties, e.g., those that minimize the number of factors or consist of factors with similar lengths. In this paper, we consider the problem of finding an alphabet ordering that yields a Lyndon factorization with such properties. We introduce a flexible evolutionary framework and evaluate it on biological sequence data. For the minimization case, we also propose a new problem-specific heuristic, Flexi-Duval, and a problem-specific mutation operator for Lyndon factorization. Our results show that our framework is competitive with Flexi-Duval for minimization and yields high quality and robust solutions for balancing where no problem-specific algorithm is available.