Palindromic Decompositions with Gaps and Errors
Department of Computer Science
King's College London
University of London
Speaker 2: Miss Mai Alzamel
PhD student of the Department of Informatics
King's College London
University of London
Speaker 3: Mr Panagiotis Charalampopoulos
Research student of the Department of Informatics
King's College London
University of London
COM2 Level 2
MR3, COM2-02-26
Abstract:
Identifying palindromes in sequences has been an interesting line of research in recent years after the discovery of the relation of palindromes in the DNA sequence with the HIV virus. Efficient algorithms for the decomposition of sequences in palindromes and maximal palindromes have been devised in recent years. We extend these studies by imposing a lower bound to the length of acceptable palindromes and allowing gaps and errors in the decompositions. We present an algorithm for obtaining such a palindromic decomposition with the minimal total gap length in time O(ng log n), where n is the length of the input string and g the number of allowed gaps. We further present an O(ng)-time algorithm for the decomposition in maximal palindromes with g allowed gaps and discuss the introduction of errors in this version of the problem.
Speaker 1 - Biodata:
Costas Iliopoulos received his PhD in 1983 from Warwick University and he established the Algorithm Design Group at King's College London in 1991.His field of expertise is the theory and practice of algorithmics, in areas including pattern matching,repetition and regularity finding,text compression, and automata theory and applications. He works on several fields from molecular sequence analysis,computer vision,symbolic computation & music. He developed new data structures for order-preserving matching, new methods for finding Abelian regularities, subtree repeats, quasiperiods, cubic runs, tandem repeats. Costas is the editor-in-Chief of the Journal of Discrete Algorithms (Elsevier) and he has served as chair and member of numerous programme committees of international conferences and workshops.
Speaker 2 - Biodata:
Mai Alzamel is a Ph.D. student under the supervision of Prof. Costas S. Iliopoulos, in the Department of Informatics, King's College London. She studied her M.Sc. in Advanced Computer Science, University of Sheffield, UK. Mai?s research focuses on the design and analysis of efficient algorithms and data structures for sequential data (Stringology). She published several papers about circular strings and signal processing. She currently is a student member at Centre for Combinatorics on Words & Applications (Murdoch University, Perth, Australia). She was a member of the organising committee of student conference MatBio 2016 and LSD and Law 2016. Mai is currently a member of the organiser committee of LSD and Law 2017 and a member of the scientific committee of StringMasters 2016, Palermo, Italy.
Speaker 3 - Biodata:
Panagiotis Charalampopoulos is a Ph.D. student under the supervision of Prof. Costas S. Iliopoulos, in the Department of Informatics (Faculty of Natural & Mathematical Sciences), King's College London, where he previously completed his M.Sc. in Advanced Computing. He holds a BA in Mathematics from the University of Cambridge and has worked for a couple of years as an advisor in Data Analytics in Ernst & Young. His research focus is the design and analysis of algorithms for strings and data structures for sequential data (Stringology), as well as combinatorics on words.