Evolutionary Search Techniques for the Lyndon Factorization of Biosequences

Research output: Contribution to conferencePaperpeer-review

5 Citations (SciVal)
448 Downloads (Pure)

Abstract

A non-empty string x over an ordered alphabet is said to be a Lyndon word if it is alphabetically smaller than all of its cyclic rotations. Any string can be uniquely factored into Lyndon words and efficient algorithms exist to perform the factorization process in linear time and constant space. Lyndon words find wide-ranging applications including string matching and pattern inference in bioinformatics. Here we investigate the impact of permuting the alphabet ordering on the resulting factorization and demonstrate significant variations in the numbers of factors obtained. We also propose an evolutionary algorithm to find optimal orderings of the alphabet to enhance this factorization process and illustrate the impact of different operators.
The flexibility of such an approach is illustrated by our use of five fitness functions which produce different factorizations suitable for different downstream tasks.
Original languageEnglish
Pages1543-1550
Number of pages8
DOIs
Publication statusPublished - 13 Jul 2019
EventWorkshop on Evolutionary Computation for Permutation Problems at GECCO 2019 - Prague, Czech Republic
Duration: 13 Jul 201917 Jul 2019
Conference number: 3
http://www.sc.ehu.es/ccwbayes/gecco2019_permutations/scheduling.html

Workshop

WorkshopWorkshop on Evolutionary Computation for Permutation Problems at GECCO 2019
Country/TerritoryCzech Republic
CityPrague
Period13 Jul 201917 Jul 2019
Internet address

Keywords

  • Algorithm
  • Alphabet
  • Artificial intelligence
  • Burrows-Wheeler transform
  • Evolutionary search
  • Factorization
  • Genome
  • Lyndon word
  • Pattern matching
  • String
  • Word

Fingerprint

Dive into the research topics of 'Evolutionary Search Techniques for the Lyndon Factorization of Biosequences'. Together they form a unique fingerprint.

Cite this