Evaluation of a Permutation-Based Evolutionary Framework for Lyndon Factorizations

Lily Major, Amanda Clare, Jacqueline Daykin, Benjamin Mora, Leo Peña Gamboa, Christine Zarges

Allbwn ymchwil: Pennod mewn Llyfr/Adroddiad/Trafodion CynhadleddTrafodion Cynhadledd (Nid-Cyfnodolyn fathau)

2 Dyfyniadau (Scopus)
171 Wedi eu Llwytho i Lawr (Pure)

Crynodeb

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.
Iaith wreiddiolSaesneg
TeitlParallel Problem Solving from Nature – PPSN XVI - 16th International Conference, PPSN 2020, Proceedings
Is-deitl16th International Conference, Leiden, The Netherlands, September 5-9, 2020, Proceedings
GolygyddionThomas Bäck, Mike Preuss, André Deutz, Michael Emmerich, Hao Wang, Carola Doerr, Heike Trautmann
CyhoeddwrSpringer Nature
Tudalennau390-403
Nifer y tudalennau14
ISBN (Electronig)9783030581121
ISBN (Argraffiad)9783030581114
Dynodwyr Gwrthrych Digidol (DOIs)
StatwsCyhoeddwyd - 31 Awst 2020
DigwyddiadParallel Problem Solving Nature - Leiden, Yr Iseldiroedd
Hyd: 05 Medi 202009 Medi 2020
Rhif y gynhadledd: 16
https://ppsn2020.liacs.leidenuniv.nl

Cyfres gyhoeddiadau

EnwLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Cyfrol12269 LNCS
ISSN (Argraffiad)0302-9743
ISSN (Electronig)1611-3349

Cynhadledd

CynhadleddParallel Problem Solving Nature
Teitl crynoPPSN
Gwlad/TiriogaethYr Iseldiroedd
DinasLeiden
Cyfnod05 Medi 202009 Medi 2020
Cyfeiriad rhyngrwyd

Ôl bys

Gweld gwybodaeth am bynciau ymchwil 'Evaluation of a Permutation-Based Evolutionary Framework for Lyndon Factorizations'. Gyda’i gilydd, maen nhw’n ffurfio ôl bys unigryw.

Dyfynnu hyn