Theses supervised by Prof. Dr. Uğur Doğrusöz
12 theses · İhsan Doğramacı Bilkent University
Ortaklaşa yolak kürasyon aracı Pathwaymapper'a iyileştirmeler
Information visualization focuses on visually representing abstract data to amplify human cognition. Graph visualization is one of the most common types in the field of information visualization because of its capabilities to present huge amount of data in a clear and meaningful manner. A graph is a suitable data structure for representing relational information and for this reason graph visualization has a wide usage in biological pathway visualization as well. In this thesis, we focus on collaborative construction of cancer pathways and visualization of cancer genomics data overlaid over such networks. Several biological pathway visualization tools have been developed to help biologists analyze cancer genomics data, using various formats, including standard formats like SBGN, in the past. Nevertheless, most biologists prefer curated pathway diagrams like the ones featured in The Cancer Genome Atlas (TCGA) manuscripts, using a simpler notation. These pathway diagrams outline the alterations occurring in pathways for different cancer types. To address this need, a web-based tool called PathwayMapper was previously developed. PathwayMapper can be used to view pre-curated cancer pathways or to create new pathways from scratch. It has many features including overlay of genomic alteration data from the cBioPortal. It also includes a collaborative mode so that the users can interactively create and modify the cancer pathways. With this thesis, we improve PathwayMapper in several ways to make it a more complete and powerful editor with a better user interface. New features include complexity management operations, edge bend support, interactive node resize, and various highlighting capabilities. Furthermore, the user interface has been improved to be more user friendly with the addition of a toolbar.
Çizge veri tabanında depolanan sbgn haritalarının etkili sorgulanması
Graph visualization is an important research area that endeavors to make graphs more understandable and easier to analyze. In various domains, graph visualization techniques and standards are developed to effectively analyze underlying graph based data. Systems Biology Graphical Notation (SBGN) is a standard language for modeling biological processes and pathways through graph visualization. Information about SBGN maps can be stored in XML based SBGN-ML files. libSBGN is a Java/C++ library for reading, writing SBGN-ML and manipulating SBGN maps in an object-oriented manner. Graph databases store data in terms of a graph structure consisting nodes and their relationships. Performing a computation on graph data stored in a graph database by traversals is more efficient than accessing tabled data in relational databases through costly join operations. Neo4j is a prominent graph database that provides a proprietary language named Cypher for querying stored graph data. Neo4j allows writing user defined procedures in Java as plugins to improve capabilities of Neo4j with third party Java libraries. With this thesis, we enable modeling SBGN maps in Neo4j graph database with support for compound structures. Using this SBGN data model in Neo4j, we developed graph based user defined procedures in Java using libSBGN as a plugin to Neo4j. These procedures were used to implement graph query algorithms, such as neighborhood, common stream, and paths between, along with helper functions such as populating a database from an SBGN map and loading an SBGN map from a graph database. These user defined procedures are designed to produce or consume SBGN-ML; hence, they can be used by any visualization tool which can import/export SBGN-ML text. Newt, a web based editor for viewing and editing SBGN maps, is such a tool making use of these procedures and hosting a local Neo4j instance by providing a web service to execute Cypher statements.
SBGN notasyonunu kullanan biyolojik haritalar ̇için anlamsal dogrulama
Graph visualization is a research field where relational information is graphically represented in the form of graphs or networks. It is applicable in numerous areas from computer network systems, to biology, to software engineering. In such areas, graph visualization techniques provide effective visual analysis of graph based data. Systems Biology Graphical Notation (SBGN) facilitates a standard model for representing biological entities and their interactions by using graph visualization. SBGN-ML is an XML based format for keeping information about SBGN maps. libSBGN enables writing and reading SBGN-ML files in an easy manner and is meant to bring syntactic and semantic validation to SBGN maps. It is currently available in Java/C++ (libSBGN) and JavaScript (libSBGN.js) programming languages with varying support for aforementioned. libSBGN enables important syntactic and semantic correctness concepts for manipulating SBGN maps and converting SBGN-ML files into several other formats. Syntactic validation of SBGN-ML files involves using a simple XML Schema Definition (XSD) file. This validation checks whether files are in correct form or not. However, this XSD file does not enable checking against semantic rules. For semantic validation of such files, the Schematron language was developed providing higher level semantic rule controls. With this thesis, we first enabled high level semantic validation (schematron validation) of SBGN maps in libSBGN.js, which uses XSLT and transformation of process description maps in SBGN-ML files. By using Schematron rules which are written in XPath syntax and enabling human-readable messages of validation errors and source of errors, we developed an XSLT stylesheet. We obtained validation result report by transforming SBGN-ML files using this XSLT stylesheet. In the JavaScript version of libSBGN library, we used a web based XSLT processor for transformation; hence, this library is now available for providing schematron validation in any SBGN related software. Furthermore, we added schematron validation checks to Newt, a web based SBGN pathway editor, using the updated libSBGN.js library. With this addition, Newt is now able to show validation results not only in a human-readable message text for the current map but also highlights the invalid map objects graphically, and, where appropriate, suggests a way to fix the problem automatically.
Bağlantı kısıtlarını destekleyen bileşik çizge yerleştirme algoritması
Information visualization is a field of study that aims to represent abstract data in an aesthetically pleasing and easy to comprehend visual manner. Various approaches and standards have been created to reinforce the discovery of unstructured insights that are limited to human cognition via visual depictions. Complex systems and processes are often modelled as graphs since it would be difficult to describe in text. A type of visualization, graph drawing, addresses the notion of creating geometric representations of graphs. There are plentiful research directed to designing automatic layout algorithms for visualizing graphs. Nevertheless, a limited number of studies utilize ports, which are dedicated connection points on the locations where edge ends link to their incident nodes. We propose a new automatic layout algorithm named CoSEP supporting port constraints on compound nodes used for nested levels of abstractions in data.The CoSEP algorithm is based on a force-directed algorithm, Compound Spring Embedder (CoSE). Additional heuristics and force types are introduced on top of existing physical model. Using CoSE's layout structure as a baseline enables CoSEP to handle non-uniform node sizes, arbitrary levels of nesting, and inter-graph edges that may span multiple levels of nesting. Our experiments show that CoSEP significantly improves the quality of the layouts for compound graphs with port constraints with respect to commonly accepted graph drawing criteria, while running in at most a few seconds, suitable for use in interactive applications for small to medium sized graphs. The CoSEP algorithm is implemented in JavaScript as a Cytoscape.js extension, and the sources along with a demo are available on the associated GitHub repository.
Vısuall: Görsel çizge analizi bileşenlerini hızlıca başlatmak için çabuk özelleştirilebilir bir kütüphane
Graph visualization is an area of information visualization, where relational data is depicted in the form of nodes (objects) and edges (links). Many people or organizations utilize graph visualization for insightful analysis and interpretation of relational data. In graph visualization, primary challenges include complexity management, efficient database querying, and customization for specific domains. Visu\textit{all} aims to solve these problems by providing a generic, highly customizable, and easily configurable software component for building web-based visual graph analysis tools. Essential functionalities needed by such visual analysis components include manually or automatically setting the layout of graph elements, support for nested or hierarchical drawings, efficient querying of the database or client-side data, emphasizing or highlighting graph elements of interest, customization of visuals and styles, clustering, calculating graph-theoretical properties, and time-based filtering of graph elements. Although Visu\textit{all} provides all these functionalities out of the box for jumpstarting, customization of software for domain-specific needs is still unavoidable. Such software changes might result in complications due to unstructured code and code ignoring the invariants assumed by the original development team. To prevent these and to facilitate easily maintainable customization, Visu\textit{all} provides a modular architecture. Furthermore, the developers straightforwardly upgrade the software so long as the Visu\textit{all} developers and the users developing visual analysis components based on Visu\textit{all} maintain the provided architecture. We tested our database queries on a database that contains about half a million graph elements. We also examined our client-side operations up to a thousand graph elements. In both client-side and database operations, we observe that operations take at most several seconds, making Visu\textit{all} convenient for interactive exploration and analysis of networks.
Küçük bileşik çizgeler için dikey düzen yerleştirme algoritması
Information visualization is the study of different approaches that aid in the visualization and examination of data. Among the broad variety of different options and techniques available in this field is ``Graph Drawing", which is regarded as the algorithmic foundation of relational information or graph visualization. Graph drawing fuses graph theory and visualization for presenting data as geometric shapes and for laying them out in a 2-D or 3-D space. There exist many different types of automatic graph layouts. One such layout is the orthogonal graph layout in which edges are made up of horizontal and vertical segments. A specialized version of graphs called compound graphs are used to represent grouping or clustering of graph objects. Many orthogonal layout approaches have been presented for simple graphs but there is considerably less research available for orthogonal layout algorithms for compound graphs. In this thesis, we present C-TSM, which takes the already existing Topology-Shape-Metrics (TSM) approach and extends it to cater to 4-degree small compound graphs with uniform node sizes. First, compound graphs are converted to simple graphs and then the TSM approach is applied to it. The resulting output is compacted again in a post-processing step and then the graph is converted back to a compound graph. The results of performance tests on our algorithm show that C-TSM works considerably well on small-sized graphs and gives the output in up to a few seconds. This algorithm has been implemented in Javascript and Python and is available as a Cytoscape.js extension. The source code and a demo application are available on a GitHub repository.
Kısıt destekli hızlı bileşik çizge yerleştirme
Visual analysis of relational data becomes more challenging in today's world as the amount of data increases exponentially. Effective visual display of such data is therefore a key requirement to simplify the analysis process. Compound graphs present a practical structure for both representing the relational data with varying levels of groupings or abstractions and managing its complexity. In addition, a good automatic layout of these graphs lets users understand relationships, uncover new insights and find important patterns hidden in the data. To this end, we introduce a new layout algorithm named fCoSE (fast Compound Spring Embedder) for compound graphs with support for user-specified placement constraints. fCoSE combines the speed of spectral layout with the aesthetics and quality of force-directed layout while satisfying specified constraints and properly displaying compound structures. The algorithm first generates a draft layout with the help of a spectral approach, then enforces placement constraints by using newly introduced heuristics and finally polishes the layout via a force-directed layout algorithm modified to maintain enforced constraints. Our experiments performed on both real-life and randomly generated graphs verify that fCoSE outperforms its competitors in terms of both speed and generally accepted graph layout criteria and is fast enough to be used in interactive applications with small to medium-sized graphs.
CMGV: Çizge görselleştirmede karmaşıklık yönetimi için birleşik bir çerçeve
In today's era of technological revolution, the sheer volume of data being produced poses a significant challenge for analyzing relational data of such scale, particularly in terms of visual analysis. Graphs provide an effective way of organizing and representing relational data, with nodes representing entities. In contrast, edges representing relationships, a comprehensive and intuitive view of complex large-scale data is created. A well-represented visualization of complex graphs allows users to understand relationships, uncover new insights, and discover hidden patterns. To this end, we introduce a complexity management framework for effectively analyzing large-scale relational data represented as graphs. Existing methods for managing graph complexity work independently and may lead to inconsistencies and confusion consecutively applied. The Complexity Management Graph Visualization framework (CMGV) presents a novel approach integrating commonly used complexity management techniques while ensuring the preservation of the user's mental map through a specialized layout algorithm. The framework introduces an intuitive Graph Complexity Management Model (CMGM) for both graph representation and complexity management. CMGV supports commonly utilized complexity management tasks, including filtering, hiding, showing, collapsing, and expanding graph elements. Importantly, CMGV is designed to be independent of the rendering method and can be seamlessly integrated with different graph rendering libraries. This is possible through an extension that synchronizes the graph models between the rendering library and CMGM. Our experiments performed on randomly generated graphs verify that CMGV flawlessly performs consecutive graph complexity management operations, leaving the user graph intact, and outperforms existing complexity management solutions in terms of both runtime and generally accepted graph layout criteria. It is fast enough to be used in interactive applications with small to medium-sized graphs.
Kanser genomik bilgisinin yolaklar dahilinde analizini sağlayan yazılım araçları
Veri Görselleme soyut olarak temsil edilmiş bilginin, insan algısını destekleyecek, etkili bir biçimde görsel olarak temsil edilmesini hedefler. Çizgeler ilişkisel bilginin temsil edilmesi için tercih edilen uygun yapılardır. Bir çizgenin görsellenmesi çizgenin yapısındaki ilişkisel bilginin daha iyi anlaşılması ve çözümlenmesi bakımından fayda sağladığı için önemlidir. Biyolojik yolak görselleme¸ Çizge görsellenmesinin yaygın olarak kullanıldığı bir alandır. Kanser ile ilişkili yolakların ilgili kanser genomik bilgisi dahilinde interaktif bir biçimde çözümleme ve görsellenmesi, örn: TCGA projesi dahilinde erişilebilen yolaklar, araştırmacılar için hastalıkların olası nedenlerini anlamak, neden sonuç ilişkilerini gözlemlemek adına değerli bilgiler sunar. Bu yolakların boyutu ve karmaşıklığı ve de ilgili genomik datanın boyutu arttıkça, daha etkili karmaşıklık yönetim teknikleri, etkili ve gelişmiş çizge görsellemeleri, bilgisayar ortamında kolay olarak paylaşıma olanak sağlayan bilgi temsilleri araştırmacıların neden sonuç ilişkilerini daha iyi çözümlemesine imkan sağlar. Bu tez çalışması kapsamında genomik datanın yolaklar dahilinde görsellenmesini sağlayan yazılım bileşenleri tasarlanmış ve gerçekleştirilmiştir. Bu yazılım bileşenleri özel olarak cBioPortal for Cancer Genomics (cBioPortal) isimli, kanser araştırmalarında yaygın olarak kullanılan web tabanlı bir yazılım dahilinde genlerin birbirleriyle ilişkilerini gösteren düzenleyici yolakları ve moleküler seviyede prosesleri görselleyebilmek için hayata geçirilmiştir. cBioPortal dünya çapında aylık olarak yaklaşık 60.000 kişi tarafından ziyaret edilen, büyük çapta kanser genomik bilgisinin görsellenmesi¸ çözümlenmesi ve indirilmesi hizmetleri veren web tabanlı bir yazılımdır. cBioPortal dahilinde geliştirilen çizge görselleme bileşeni, verilen bir gen listesinin , bir kanser tipi dahilinde etkileştiği diğer genleri içeren komşuluk yolaklarını kanser genomik bilgisiyle beraber etkili bir biçimde görselleyebilmektedir. Buna ek olarak çeşitli filtreleme ve karmaşıklık yönetimi olanakları da ( örn: genomik alterasyona göre çizge köşelerini filtreleme, gen etkileşimlerini alındığı veri tabanına göre filtreleme) bu yazılım bileşeni dahilinde hayata geçirilmiştir. Istenildiği takdirde gen etkileşimleri daha detaylı bir şekilde, moleküler seviyede prosesler dahilinde Systems Biology Graphical Notation (SBGN) diye ad- landırılan bir notasyonla görsellenebilmektedir. Bu detaylı proses seviyesinde olan yolak bilgisi Pathway Commons isimli yolak veritabanından bir sorguyla, SBGN proses dili diye adlandırılan bir dilde alınmaktadır. Son olarak, özellikle TCGA yayınlarında sıkça rastlanan ve yaygın olarak kullanılan bir notasyonda yolakların görsellenmesi ve oluşturulması amacıyla yeni bir yolak görselleme aracı tasarlanmış ve geliştirilmiştir. Bu yazılım aracı standard bir çizge görselleme ve oluşturma aracından farklı olarak, ortak olarak bir TCGA yolağının araştırmacılarca oluşturulmasına olanak sağlamaktadır.
İyileştirilmiş bir bileşik çizge yerleştirme algoritması
Interactive graph editing plays an important role in information visualization systems. For qualified analysis of the given data, an automated layout calculation is needed. There have been numerous results published about automatic layout of simple graphs, where the vertices are depicted as points in a 2D or 3D plane and edges as straight lines connecting those points. But simple graphs are insufficient to cover most real life information. Relational information is often clustered or hierarchically organized into groups or nested structures. Compound spring embedder (CoSE) of Chisio project is a layout algorithm based on a force-directed layout scheme for undirected, non-uniform node sized compound graphs.In order to satisfy the end-user, layout calculation process has to finish fast, and the resulting layout should be eye pleasing. Therefore, several methods were developed for improving both running time and the visual quality of the layout. With the purpose of improving the visual quality of CoSE, we adapted a multi-level scaling strategy. For improving the performance of the CoSE, the grid-variant algorithm proposed by Fruchterman and Reingold and parallel force calculation strategy by using graphics processing unit (GPU) were also adopted. Additionally, tuning of the parameters like spring constant and cooling factor were considered, as they affect the behavior of the physical system dramatically. Our experiments show that after some tuning and adaptation of the methods above, running time decreased and the visual quality of the layout improved significantly.
Telekomünikasyon ağlarında sesli olta saldırılarının birleşik sınıflandırma modeli ile tespiti ve görsel analiz aracına entegrasyonu
Voice phishing, a method of social engineering fraud performed over phone calls, has been a major problem globally since the use of phones became widespread. Traditional and modern methods to detect these fraud schemes include visual analysis of the customers' behaviour, rule-based systems and machine learning models such as clustering, decision trees, shallow classifiers and deep learning models. Visual analysis depends only on human expertise and requires very high labor force to be effective. Rule-based systems are useful for extreme cases but are vulnerable to concept drifts. The-state-of-the-art methods generally utilize machine learning approaches. However, they require one or more of feature engineering done by experts, high computational power and privacy infringements. Therefore, in collaboration with Turkcell Technology, we aimed to develop a system that benefits from the advantages of the traditional methods while exploiting the effectiveness and efficiency of the state-of-the-art ones to tackle this issue. In doing so, we integrated an ensemble learning model to an existing visualization tool for detecting fraud users. This tool visualizes relational data as knowledge graphs, shows the informational data as texts and statistical data with charts and texts. Our ensemble learning model has two deep neural networks and one decision tree classifier. Multiple neural networks are used to reduce the variance and make a more stable model. One of them is composed of an input layer, two hidden layers with 200 nodes using Rectified Linear Unit (ReLU) activation function, each followed by a dropout layer and an output layer of one node with sigmoid activation function. We used dropout layers in this network to prevent over-fitting. The second neural network we built has 3 hidden layers instead with node numbers 64, 64 and 32, respectively, with ReLU as their activation function. To feed these models, a total of 34 features, 20 of which are raw, have been engineered with Turkcell fraud experts. The aggregation of the outputs is done by taking their average. We measured the success of our model by calculating the F1 Score as the class imbalance is high. Our model's F1 score is 0.82 with a precision of 0.82 and a recall of 0.83. Also, with the integration of our model into this visualization tool, a framework was formed allowing mobile network operators to examine and detect fraud cases more efficiently and act accordingly.
Hyse: Hibrit çizge yerleşimi için yay bazlı yaklaşım
In recent times, the growth of data has been exponential, making the visual analysis of relational data progressively complex. Presenting such data in a visually appealing manner can help simplify the analysis process. Hybrid graphs, comprising a central directed or hierarchical part and interconnected undirected components, offer a practical structure for representing relational data with varying levels of abstraction while managing its complexity. To comprehend the relationships in data, discover insights, and get important patterns, a well-optimized graph layout for such graphs is needed. In response, we present HySE (Hybrid Spring Embedder), a novel graph layout algorithm tailored for hybrid graphs. HySE makes use of a holistic approach based on the popular spring embedder to achieve the aesthetics and quality of an optimized force-directed layout, not only on the undirected part of the graph but also on the hierarchy while maintaining the cohesion between both directed and undirected elements of the graph. The layout algorithm assumes the rank information of directed graph elements is already calculated with one of the popular approaches. Then, it finds appropriate initial positions and uses a force-directed layout technique to integrate the undirected parts into the layout, applying spring forces to model the edges, and repulsive electric forces for the nodes. Iteratively, HySE converges to an equilibrium state with minimized energy, resulting in visually pleasing and interpretable layouts for intricate hybrid graphs. Experiments performed on graphs, generated randomly through a well-designed process, validate that HySE performs as well as the state-of-the-art algorithms in terms of quality. It also matches the speed of well-established algorithms as well in small-to-medium-sized graphs.