Talk by Jan Holub on pattern matching in genomes

Talk by Jan Holub, Exact and Approximate Pattern Matching in Genomes, on Tuesday November 1, at 6pm, in Sierra 1422.

Bio: Jan Holub is a professor at Faculty of Information Technology in Czech Technical University in Prague. He leads a research group called the Prague Stringology Club and organizes annual conference Prague Stringology Conference. He received his Ph.D. in 2000. He spent some time in University of Marne-la-Vallee, France, McMaster University, Canada, Ecole polytechnique, France, and Aalto University, Finland. Currently he is a Fulbright scholar at Pennsylvania State University, USA. His research interests cover stringology (computer science about algorithms over strings), data compression, and bioinformatics.


Talk by Ariel Fernandez on Sep 26

I am very happy to host my former PhD student Ariel Fernandez, who is going to give a talk on Monday Sep 26, at 6pm, in Broome Library 1360. Below is the biographical sketch of Ariel, and the abstract of his talk.

Bio sketch of Ariel Fernandez: I did my PhD at the McMaster University, under the supervision of Michael Soltys-Kulinicz. My research is in the area of proof complexity and algorithms, especially inspired by the subject of Combinatorial Matrix Theory, which combines linear algebra, graph theory, and combinatorics, and has a rich algorithmic content. Also I am interested in Cryptography & Security, in particular in Lattice Based Cryptography, and I was part of the research group FRAISE. Recently I have also become interested in Quantum Computing, and especially in the study of quantum concepts in Proof Complexity.

From 2013 I am working on the cartographic industry and Geographic Information Systems (GIS systems), I became the CEO of a maps making company called “Filcar SRL” running my business in Buenos Aires, Argentina. The company is dedicated to design maps, routes, and streets guidance.”

Abstract : This presentation is twofo9-26-2016-grad-seminar-posterld:

On one side, we talk about what is Combinatorial Matrix Theory (CMT), what is Proof Complexity, and we show how to combine this two fields, in order to present a feasible framework to analyze and formalize concepts in CMT. We take a proof-complexity approach to formalize Mini-Max type of reasoning within our framework. And finally, we present a new Permutation Based Algorithm which arise from taking a CMT-approach to an important problem in Matching Theory.

On the other side, I am going to expose my PhD experiences, addressing some questions about why I decided to do a PhD, what were the different stages of the process of doing my PhD, which obstacles that I have faced, and how I exceeded. Finally, I would like to expose how and what I learned in my PhD that helps me to run a better business in my country.

Talk at PSC2016 on paper with Neerja Mhaskar

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

Slides are attached:

Some other pictures:

CS talk today: Slashed graph representation in design & control problems

IMG_2462Title: Distributed graph models and transformations – slashed graph representation in design and control problems

[Presentation Slides]

Speaker: Adam Sędziwy, PhD, AGH University of Science and Technology, Kraków, Poland

Time: Thursday, June 9, 2016, at 11am

Place: Sierra Hall 1422

Abstract: Graph based structures play the important role in all domains of science: structure of physical objects, logical structure of abstract entities, functional and logical dependencies among them, data and process flows, dynamics of systems and many, many other phenomena can be  successfully described by graphs and hypergraphs. Practical application of graphs, however, meets constraints related to the complexity. They can be reduced to such common known problems as subgraph isomorphism problem, existence of k-clique, Hamiltonian path problem and others.

In this talk I will present the summary of the research on methods being a workaround to graph-related complexity issues. Obtained results enable practical application of graph-based models to problems inducing the graphs having tens of thousands of vertices. The application of presented methods to real-life cases will illustrate the presentation.

Bio: Adam Sędziwy (MSc, PhD, DSc (in completion) in computer science, MSc in theoretical physics) is an assistant professor in Dept. of Applied Computer Science, AGH University of Science and Technology, Kraków, Poland. His area of interest includes distributed graph transformations relied on multi-agent systems, and their applications. He also focuses on advanced methods of outdoor lighting design and control yielding highly energy-efficient SSL-based roadway lighting installations. He cooperates with lighting solutions vendors such as GE Lighting, Schreder, Philips. He is author and co-author of nearly 60 research publications. URL:

Comp Sci Bioinformatics talk on Tuesday April 12 in Broom 1310

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.

Computer Science Talk in Mobile Robotics

On November 4th, at 6pm, in the Petit Salon, Computer Science is organizing an event to which everyone is invited, especially current and prospective graduate students. There is going to be food, good company, and an exciting talk by Dr. Quintero (see ad below). For more information, please contact David Claveau <>.