Theses supervised by Doç. Dr. Uğur Doğrusöz
10 theses · İhsan Doğramacı Bilkent University
Kesişen kümelenmiş çizgeler için bir yerleştirme algoritması
Graphs are often used for visualizing relational data such as social or biological networks. Numerous methods have been proposed for automatic layout of simple graphs. However, simple graphs are usually insufficient in displaying relational information, since relational information is often clustered. Clustering models traditionally assume that each data point belongs to one and only one cluster; however, in complex networks, these clusters often overlap. For effective visualization of clustered graphs, the nodes in the same cluster should be placed together, respecting general graph drawing criteria such as avoiding node-node overlaps, minimizing edge crossings, and minimizing the total drawing area. Clustered graph layout problem becomes even more challenging when cluster overlaps are allowed. Here, we present a new algorithm for automatic layout of graphs with overlapping clusters based on force directed layout approach. The graph is fi rst divided into zones according to clusters and their intersections, and new additional forces are introduced to the traditional spring embedder algorithm to keep nodes in the same cluster together, trying to keep neighboring nodes in separate clusters at a safe distance. Spring constants had to be fine-tuned to achieve a fast and eff ective layout operation. The algorithm was implemented and validated within a new layout style named Cluster Layout in the layout module of ChiEd visualization tool.
SBGN proses diyagramlarının yönetimi ve gösterimi için geliştirilen metotlar ve araçlar
Graphs are commonly used to model relational information in many areas such as relational databases, software engineering, biological and social networks. In vi- sualization of graphs, automatic layout, interactive editing and complexity man- agement of crowded graphs are essential for effective utilization of underlying information. Advances in graphical user interfaces have given rise and value to interactive editing and diagramming techniques in graph visualization. As the size of the information to be visualized vastly increased, it became harder to analyze such networks, making use of relational information needed to be acquired. To over- come this problem, sophisticated and domain-specific complexity management techniques should be provided. The Systems Biology Graphical Notation (SBGN) has been developed over a number of years by biochemists and computer scientists to standardize visual representation of biochemical and cellular processes. SBGN introduces a concrete, detailed set of symbols for scientists to represent network of interactions, in a way that is not open to more than one interpretation. It also describes the manner, in which such graphical information should be interpreted. The SBGN Process Description (PD) language shows how entities are influ- enced by processes, which are represented by several reaction types in a biological pathway. It can be used to show all the molecular interactions taking place in a network of biochemical entities, with the same entity appearing multiple times in the same diagram. We developed methods and tools to effectively visualize and manage SBGN- PD diagrams. Specifically, we introduced new algorithms for proper manage- ment of complexity of large SBGN-PD diagrams. These algorithms strive to keep SBGN-PD diagrams intact as complexity management takes places. In ad- dition, we provided software components and web-based tools that implement these methods. These tools use state-of-the-art web technologies and libraries.
Systems biology graphical notation kullanılarak çizilen proses diyagramlarının otomatik yerleştirmesi
Evolving technology has increased the focus on genomics. The combination of today's advanced studies with decades of molecular biology research yield in huge amount of pathway data. These models can be used to improve high-throughput data analysis by linking correlation to the causation, shedding light on many complex diseases. In order to prevent ambiguity and ensure regularity of the research, a need for using a standard notation has emerged. Systems Biology Graphical Notation (SBGN) is a visual language developed by a community of biochemists, modellers and computer scientists with the intention of enabling scientists to represent networks, including models of cellular processes, in a standard, unambiguous way. SBGN is formed of three languages: process, entity relationship and activity flow. This research is focused on its process diagram branch. Automated layout is commonly used to clearly visualize the information represented by graphs. Considering the fact that, biological pathways includes nested structures (e.g., nucleoplasms), we have made use of a force-directed automatic layout algorithm called Compound Spring Embedder (CoSE), which supports the compound graph structures. On top of this layout structure, we have developed a specialized layout algorithm called SBGN-PD layout. SBGN-PD layout enhancements mainly include properly tiling of complex members and disconnected molecules, placement of product and substrate edges on the opposite sides of a process node without disturbing the force-directed structure of the algorithm.
Çizge tabanlı yolak veri tabanlarının etkin sorgulanması için algoritmalar
As the scientiï¬c curiosity shifts toward system-level investigation of genomic-scale information, data produced about cellular processes at molecular level hasbeen accumulating with an accelerating rate. Graph-based pathway ontologiesand databases have been in wide use for such data. This representation has madeit possible to programmatically integrate cellular networks as well as investigatingthem using the well-understood concepts of graph theory to predict their struc-tural and dynamic properties. In this regard, it is essential to eï¬ectively querysuch integrated large networks to extract the sub-networks of interest with thehelp of eï¬cient algorithms and software tools.Towards this goal, we have developed a querying framework along with a num-ber of graph-theoretic algorithms from simple neighborhood queries to shortestpaths to feedback loops, applicable to all sorts of graph-based pathway databasesfrom PPIs to metabolic pathways to signaling pathways. These algorithms canalso account for compound or nested structures present in the pathway data, andhave been implemented within the querying components of Patika (PathwayAnalysis Tools for Integration and Knowledge Acquisition) tools and have provento be useful for answering a number of biologically signiï¬cant queries for a largegraph-based pathway database.Keywords: Graph Algorithms, Graph Querying, Biological Pathways, PathwayDatabases.iii
Chısıo: Bileşik çizge düzenlemesi ve yerleştirmesi için görsel bir çerçeve
Graphs are data models, widely used in many areas from networking to biology tocomputer science. Visualization, interactive editing ability and layout of graphsare critical issues when analyzing the underlying relational information.There are many commercial and non-commercial graph visualization tools.However, overall support for compound or hierarchically organized graph repre-sentations is very limited.We introduce a new open-source editing and layout framework named Chisiofor compound graphs. Chisio is developed as a free, easy-to-use and powerful aca-demic graph visualization tool, supporting various automatic layout algorithms.It is written in Java and based on Eclipse?s Graphical Editing Framework (GEF).Chisio can be used as a ï¬nished generic compound graph editor with standardgraph editing facilities such as zoom, scroll, add or remove graph objects, move,and resize. Object property and layout options dialogs are provided to modifyexisting graph object properties and layout options, respectively. In addition,printing or saving the current drawing as a static image and persistent storagefacilities are supported. Saved graphs or GraphML formatted ï¬les created byother tools can be loaded into Chisio. Furthermore, a highlight mechanism isprovided to emphasize subgraphs of users interest.The framework has an architecture suitable for easy customization of the toolfor end-users? speciï¬c needs as well. Also Chisio oï¬ers several layout styles fromthe basic spring embedder to hierarchical layout to compound spring embedder tocircular layout. Furthermore, new algorithms are straightforward to add, makingChisio an ideal test environment for layout algorithm developers.iiiivKeywords: information visualization, graph layout, graph editing, software sys-tem, graph editor, compound graphs.
Kümelenmiş çizgeler için çembersel yerleşim algoritması
Visualization of information is essential for comprehension and analysis of the acquired data in any field of study. Graph layout is an important problem in information visualization and plays a crucial role in the drawing of graph-based data. There are many styles and ways to draw a graph depending on the type of the data. Clustered graph visualization is one popular aspect of the graph layout problem and there have been many studies on it. However, only a few of them focus on using circular layout to represent clusters. We present a new, elegant algorithm for layout of clustered graphs using a circular style. The algorithm is based on traditional force-directed layout scheme and uses circles to draw each cluster in the graph. In addition it can handle non-uniform node dimensions. It is the first algorithm to properly address layout of the quotient graph while considering inter-cluster relations as well as intra-cluster edge crossings. Experimental results show that the execution time and quality of the produced drawings with respect to commonly accepted layout criteria are quite satisfactory. The algorithm has been successfully implemented as part of Chisio, version 1.1. Chisio is an open source general purpose graph editor developed by i-Vis (information visualization) Research Group of Bilkent University.
VISIBIOweb : Biyolojik yolaklar için web tabanlı görselleme ve mizanpaj servisi
A biological pathway is a representation of biological reactions between molecules in a living cell. At present, there are hundreds of Internet-accessible databases storing biological pathway data. Exchanging, handling, and storing this data are crucial in terms of both providing understandability and allowing further enhancements on the gathered data. As a result of this necessity, many biological models were developed to cluster the data in a meaningful manner under a semantically reasonable hierarchy.As the amount and complexity of the data increases, visualization of pathways becomes inevitable. Graphs are inherently suitable for modeling pathways. The task of creating a visual representation for pathways dynamically requires methods from the area of graph visualization. As a result, many software systems, which can interpret the pathway data with a graph structure and visualize the constructed graph, emerged. However, many of these software systems are insufficient due to poor complexity handling of the underlying model, lack of visual standardization or long installation steps.In this thesis, we introduce VISIBIOweb, a new open-source and web-based visualization service for biological pathway models stored in BioPAX (Biological Pathways Exchange Language) format. VISIBIOweb runs on Apache Tomcat server and is implemented in Java based on Eclipse GEF (Graphical Editing Framework). Google Maps API is used on the client side as the core component to visualize the representation constructed on the server.VISIBIOweb supports basic graph viewing functionalities such as zooming, scrolling, and selection of graph objects. The inspector window is provided to view the properties of the selected graph object. Once the view for the uploaded biological model is created, it can be stored as a static image. The biological models can also be persisted and embedded within other web sites just like Google Maps. The layout information of the constructed graph is also provided in an XML-based format. The introduction of such a format is a good starting point to develop an official layout extension for BioPAX format.
Biyolojik ağlarda nedensellik analizi
Systems biology is a rapidly emerging field, shaped in the last two decades or so, which promises understanding and curing several complex diseases such as cancer. In order to get an insight about the system - specifically the molecular network in the cell - we need to work on following four fundamental aspects: experimental and computational methods to gather knowledge about the system, mathematical models for representing the knowledge, analysis methods for answering questions on the model, and software tools for working on these. In this thesis, we propose new approaches related to all these aspects.In this thesis, we define new terms and concepts that helps us to analyze cellular processes, such as positive and negative paths, upstream and downstream relations, and distance in process graphs. We propose algorithms that will search for functional relations between molecules and will answer several biologically interesting questions related to the network, such as neighborhoods, paths of interest, and common targets or regulators of molecules.In addition, we introduce ChiBE, a pathway editor for visualizing and analyzing BioPAX networks. The tool converts BioPAX graphs to drawable processdiagrams and provides the mentioned novel analysis algorithms. Users can query pathways in Pathway Commons database and create sub-networks that focus onspecific relations of interest.We also describe a microarray data analysis component, PATIKAmad, built into ChiBE and PATIKAweb, which integrates expression experiment data with networks. PATIKAmad helps those tools to represent experiment values on network elements and to search for causal relations in the network that potentially explain dependent expressions. Causative path search depends on the presence of transcriptional relations in the model, which however is underrepresented in most of the databases. This is mainly due to insufficient knowledge in the literature.We finally propose a method for identifying and classifying modulators of transcription factors, to help complete the missing transcriptional relations in the pathway databases. The method works with large amount of expression data, and looks for evidence of modulation for triplets of genes, i.e. modulator - factor - target. Modulator candidates are chosen among the interacting proteins of transcription factors. We expect to observe that expression of the target gene depends on the interaction between factor and modulator. According to the observed dependency type, we further classify the modulation. When tested, our method finds modulators of Androgen Receptor; our top-scoring result modulators are supported by other evidence in the literature. We also observe that the modulation event and modulation type highly depend on the specific target gene. This finding contradicts with expectations of molecular biology community who often assume a modulator has one type of effect regardless of the target gene.
Chisio Web: İlişkisel bilginin uyarlanabilir görselleştirilmesi için web-tabanlı bir çerçeve
Graphs are widely used to represent complex relational information. Graph visualization is crucial for effective analysis of information. In simple graphs, nodes are generally considered as uniform-sized components and they cannot be nested. This is often not sufficient to visualize complex relationships, because relational information is often clustered or hierarchically organized into groups or nested structures.There exist many free, open source software in the field of web-based graph visualization. However, none fully supports compound or clustered graphs. Moreover, customization provided by such software is often limited to the basic visual properties of nodes and edges. It requires a lot of effort to build an advanced customization of visual properties and interactive functionality with these software.In this thesis, we introduce a free, open source, general-purpose, web-based graph visualization framework, named Chisio Web (ChiWeb). ChiWeb supports visualization, interactive editing and layout of both simple and compound graphs. ChiWeb is implemented in ActionScript language and based on Flare, which is an open source ActionScript library designed for data visualization.ChiWeb is specifically designed for easy customization with respect to visualization and functionality. ChiWeb can be used as a library to create a custom graph visualization with an advanced application behavior for particular needs of a specific domain. The elements and functionality that can be easily customized with ChiWeb are: visual styles, controls for interactive events such as node creation, key and mouse functionality, context menus, toolbars, and inspector windows. Furthermore, ChiWeb's architecture allows easy integration of new graph layout algorithms.
Biyolojik yolakların ve genomik profillerin ChiBE 2 yoluyla entegrasyonu
Biological pathways store information about spatial and temporal organization of interactions taking place in an organism. However, extracting knowledge from these pathways is not trivial as they can be huge and complicated. Additionally, simple visualization of pathways will only reveal limited knowledge. Therefore, it is critical to have tools that are specialized in analyzing and understanding biological pathways. ChiBE is one such tool that can visualize, manipulate and analyze pathway data stored in BioPAX format. There have been improvements in ChiBE regarding pathway searches, high throughput data integration, and database connections. Visual notation has been updated to follow standards in visualizations defined by the SBGN. Previously defined pathway query algorithms have been adapted to be compatible with the BioPAX model. New query types have also been designed to offer a wider range of options. With these queries, ChiBE now offers a variety of ways of pathway decomposition and thorough analysis of complex pathway views. To offer easy access to expression microarrays, a gateway to the GEO database has been added. The cBio Cancer Genomics Portal is also now reachable within ChiBE to obtain information about genomic status of various cancer cells. Furthermore, a connection to DAVID database is available, in case users want to annotate a list of genes with respect to biological terms associated with them. With these new features and improvements, ChiBE 2 has become a comprehensive tool that offers a wide range of analysis options with a genomics-oriented workflow to deepen our understanding of biological pathways.