A generic finite automata based approach to implementing lymphocyte repertoire models

Johannes Textor, Katharina Dannenberg, Maciej Liskiewicz


Artificial immune systems (AIS) inspired by lymphocyte repertoires include negative and positive selection, clonal selection, and B~cell algorithms. Such AISs are used in computer science for machine learning and optimization, and in biology for modeling of fundamental immunological processes. In both cases, the necessary size of repertoire models can be huge. Here, we show that when lymphocyte repertoire models based on string patterns can be compactly represented as finite automata (FA), this allows to efficiently perform negative selection, positive selection, insertion into, deletion from, uniform sampling from, and counting the repertoire. Specifically, for r-contiguous pattern matching, all these tasks can be performed in polynomial time. But even in NP-hard cases like Hamming distance matching, the FA representation can still lead to practically important efficiency gains. We demonstrate the feasibility and flexibility of this approach by implementing T~cell positive selection simulations based on human genomic data using four different pattern rules. Hence, FA-based repertoire models generalize previous efficient negative selection algorithms to perform several related algorithmic tasks, are easy to implement and customize, and are applicable to real-world bioinformatic problems.
Original languageEnglish
Title of host publicationGenetic and Evolutionary Computation Conference, GECCO '14, Vancouver, BC, Canada, July 12-16, 2014
Number of pages8
Publication date07.2014
ISBN (Print)978-1-4503-2662-9
Publication statusPublished - 07.2014
EventGECCO '14 Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation - Vancouver, Canada
Duration: 12.07.201416.07.2014


Dive into the research topics of 'A generic finite automata based approach to implementing lymphocyte repertoire models'. Together they form a unique fingerprint.

Cite this