Executive Summary : | Bubbles are common structures in directed graphs, appearing naturally in bioinformatics, particularly in splice graphs and string graphs. This project aims to understand bubble structures in directed graphs and develop practical algorithms to identify them in practice. Transit functions, a mathematical construct, describe abstract concepts betweenness, and the structure of bubbles naturally defines an oriented version of betweenness. The project proposes co-developing a framework for both mathematical structures, as directed transit functions apply to graphs and other structures, including hypergraphs. Technical research goals include developing a comprehensive classification of reachability and path bubbles, exploring relationships between bubbles and oriented components, developing a mathematical framework for directed transit functions, investigating bubble types and axiom systems of betweenness, investigating overlap relationships between different types, and developing efficient algorithms to identify and enumerate different types of bubble structures in general digraphs. The project also aims to apply bubble detection algorithms to digraphs arising from genome and transcriptome data analysis.
The study explores reachability and directed transit functions in graphs, focusing on the concept of "bubbles" as set systems where points inside a bubble are reachable only through the entrance and exit. The Changat group's all-path transit function for undirected graphs is a potential approach to understanding these functions. Directed transit functions can be generalized by considering natural extensions of axioms studied for undirected transit functions to the directed case. The study also investigates overlap relationships between bubbles, focusing on properties of overlaps between bubbles or transit sets. The project also applies bubble detection algorithms to digraphs arising from the analysis of genome and transcriptome data. The study investigates the dependence of detectable bubble structures on sequence depth and sequencing technology, as well as the complexity of bubble structures in transcribed loci. The study also explores the application of bubble descriptors in network science, particularly in genome assembly graphs. The study uses modern sequencing data sets for well-understood, finished genomes. |
Co-PI: | Mrs. Ameera V S, University of Kerala, Thiruvanathapuram, Kerala (691584), Dr. Arun Anil, University of Kerala, Thiruvanathapuram, Kerala (691552), Dr. Chitra M R, University of Kerala, Thiruvananthapuram, Kerala (695581) |