The CI department of Computer Science is delighted to present the following talk:
Superbubbles and Clumps
by Costas Iliopoulos, Ritu Kundu, and Fatima Vayani
Tuesday April 12th, at 10am, in Broom 1310
Presentation Slides
Abstract: The information that can be inferred or predicted from knowing the genomic sequence of an organism is astonishing. String algorithms are critical to this process. This talk provides an overview of two particular problems – superbubbles and clumps – that arise during computational molecular biology research, and recent algorithmic developments in solving them.
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 to, pattern matching, repetition and regularity finding, text compression, and automata theory and applications.The research problems he works on have many practical applications in fields varying from molecular sequence analysis,computer vision,symbolic computation & music.
Costas and his colleagues developed the most efficient (time/storage) software for mapping “Next generation Sequences”, handling the massive DNA data produced by the new sequencing hardware (Illumina) and the fastest methods/software for pairwise sequence alignment. Also, they developed the best method for hairpin identification in sequences (tropical diseases), methods for predicting the functional consequences of non-synonymous DNA sequence variants. Furthermore, they developed the Transcriptome map of mouse isochores in embryonic and neonatal cortex as well as the mouse liver, muscles & brain. In Combinatorics on words, they developed new data structures for order-preserving matching, new methods for finding Abelian regularities, subtree repeats, quasiperiods, cubic runs, tandem repeats , maximum number of squares, covers and seeds in strings and sequences.
In handling Big Data, they developed efficient parallel algorithms for mapping degenerate and weighted sequences to a reference genome, large scale DNA sequence analysis, parallel approximate string matching for massive data, storing and querying a massive number of highly similar sequences and mapping short reads to a massive number of dynamically changing genomic sequences.
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. He has held visiting positions in a number Universities: Paris Est, Pretoria, , McMaster, Rouen, Patras, Warsaw, Curtin, Stellenbosch etc. He has been supported by European Union, Royal Society, Institute of Maths, London Mathematical Society, Wellcome foundation, grants etc.
Ritu Kundu is a PhD student under the supervision of Prof. Costas S. Iliopoulos, in the Department of Informatics (Faculty of Natural & Mathematical Sciences), King’s College London, where she previously completed her M.Sc. in Advanced Computing. She has also worked as software developer for a couple of years.
Ritu’s research focusses on the design and analysis of efficient algorithms and data structures for sequential data (Stringology), which have many practical applications in fields varying from molecular sequence analysis, computer vision, symbolic computation and computational music. Her recently published works include several novel linear-time algorithms – for conservative degenerate pattern matching, for identifying super bubbles, and for discovering clumps. Some of her recently developed software-tools can be found at her GitHub profile.
She currently is a student member at Centre for Combinatorics on Words & Applications (CCWA, University, Perth, Australia) and also is acting as the web-master for International Federation for Information Processing (IFIP) Working Group 10. She is also a member of research teams of King’s College London that collaborate with CSUCI and University of Helsinki, supported by the Royal Society. She has also reviewed for LATA 2016 and MACIS 2015.
She is being funded by EPSRC DTP. In addition, she has been awarded various grants -ERASMUS+, British Council’s INSPIRE, and KCL’s Global Research Grant etc.
Fatima Vayani is a PhD student under the supervision of Prof. Costas Iliopoulos and Dr. Solon Pissis in the Department of Informatics at King’s College London. She holds a BSc in Biological Sciences and an MSc in Bioinformatics and Theoretical Systems Biology.
Her research is in the area of algorithm design, and the subsequent development of tools, for molecular sequence analysis. She has contributed to projects concerned with the alignment of circular sequences, error detection in genome assembly, pattern matching in degenerate sequences and finding the locus of the Origin of Replication in bacterial genomes.
Fatima is a member of the International Society for Computational Biology, and has been an active committee member of their Regional Student Group in the UK since 2014, helping to organise two annual student conferences. She is also a member of the Centre for Combinatorics on Words & Applications, Murdoch University (Perth, Australia) and participated in their Stringmasters workshop in 2015. She has been a member of the organising committee for London Stringology Day and London Algorithmic Workshop (LSD/LAW) since 2015. She is holds the position of events coordinator for the
International Federation for Information Processing Working Group 10. In 2015, she gave presentations at the International Symposium on Experimental Algorithms, the Workshop on Bioinformatics and Stringology at BUET, Bangladesh and Stringmasters at Murdoch University. She also gave a presentation at LSD/LAW in 2016.
Her research is funded by a Doctoral Training Award from the EPSRC. Her research visits and conference trips have been funded by The Royal Society, ERASMUS and King’s College London’s Graduate School Conference Fund, Global Research Grant and Department of Informatics.
I just gave a talk at PSC2016 conference in Prague based on a paper with Neerja Mhaskar, Forced repetitions over alphabet lists. This paper explores further the problem posed by Grytczuk in 2010 regarding the construction of non-repetitive strings over alphabet lists where each alphabet has 3 symbols. We use some string combinatorics, as well as an approach based on the Crossing sequences technique from complexity theory. The conference took place at České vysoké učeni technické v Praze – Fakulta stavebni, which is quite a mouthful to say, even for a fellow slav :), and is the Czech Technical University in Prague.
