Blog

Title: 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: http://researchgate.net/profile/Adam_Sedziwy

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.