Evolutionary Search Techniques for the Lyndon Factorization of Biosequences

Amanda Clare; Jacqueline Daykin; Thomas Mills; Christine Zarges

doi:10.1145/3319619.3326872

Evolutionary Search Techniques for the Lyndon Factorization of Biosequences

Amanda Clare, Jacqueline Daykin, Thomas Mills, Christine Zarges

Department of Computer Science

Research output: Contribution to conference › Paper › peer-review

6 Citations (Scopus)

496 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 language	English
Pages	1543-1550
Number of pages	8
DOIs	https://doi.org/10.1145/3319619.3326872
Publication status	Published - 13 Jul 2019
Event	Workshop on Evolutionary Computation for Permutation Problems at GECCO 2019 - Prague, Czech Republic Duration: 13 Jul 2019 → 17 Jul 2019 Conference number: 3 http://www.sc.ehu.es/ccwbayes/gecco2019_permutations/scheduling.html

Workshop

Workshop	Workshop on Evolutionary Computation for Permutation Problems at GECCO 2019
Country/Territory	Czech Republic
City	Prague
Period	13 Jul 2019 → 17 Jul 2019
Internet address	http://www.sc.ehu.es/ccwbayes/gecco2019_permutations/scheduling.html

Keywords

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

Access to Document

10.1145/3319619.3326872

Evolutionary Search Techniques for the Lyndon Factorization of Biosequences
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]. GECCO ’19 Companion, July 13–17, 2019, Prague, Czech Republic © 2019 Copyright held by the owner/author(s). Publication rights licensed to the Association for Computing Machinery. ACM ISBN 978-1-4503-6748
Accepted author manuscript, 2.03 MBLicence: Other

Permanent link

Persistent link

Cite this

@conference{dbaf7e1faf844a4d95b210d1e376a7c0,

title = "Evolutionary Search Techniques for the Lyndon Factorization of Biosequences",

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.",

keywords = "Algorithm, Alphabet, Artificial intelligence, Burrows-Wheeler transform, Evolutionary search, Factorization, Genome, Lyndon word, Pattern matching, String, Word",

author = "Amanda Clare and Jacqueline Daykin and Thomas Mills and Christine Zarges",

note = "Funding Information: This research was part-funded by the European Regional Development Fund through the Welsh Government, grant 80761-AU-137 (West): Publisher Copyright: {\textcopyright} 2019 Copyright held by the owner/author(s). Publication rights licensed to the Association for Computing Machinery.; Workshop on Evolutionary Computation for Permutation Problems at GECCO 2019 ; Conference date: 13-07-2019 Through 17-07-2019",

year = "2019",

month = jul,

day = "13",

doi = "10.1145/3319619.3326872",

language = "English",

pages = "1543--1550",

url = "http://www.sc.ehu.es/ccwbayes/gecco2019_permutations/scheduling.html",

}

TY - CONF

T1 - Evolutionary Search Techniques for the Lyndon Factorization of Biosequences

AU - Clare, Amanda

AU - Daykin, Jacqueline

AU - Mills, Thomas

AU - Zarges, Christine

N1 - Conference code: 3

PY - 2019/7/13

Y1 - 2019/7/13

N2 - 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.

AB - 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.

KW - Algorithm

KW - Alphabet

KW - Artificial intelligence

KW - Burrows-Wheeler transform

KW - Evolutionary search

KW - Factorization

KW - Genome

KW - Lyndon word

KW - Pattern matching

KW - String

KW - Word

UR - http://www.scopus.com/inward/record.url?scp=85070613742&partnerID=8YFLogxK

U2 - 10.1145/3319619.3326872

DO - 10.1145/3319619.3326872

M3 - Paper

SP - 1543

EP - 1550

T2 - Workshop on Evolutionary Computation for Permutation Problems at GECCO 2019

Y2 - 13 July 2019 through 17 July 2019

ER -

Evolutionary Search Techniques for the Lyndon Factorization of Biosequences

Abstract

Workshop

Keywords

Access to Document

Permanent link

Other files and links

Fingerprint

Cite this