A Customized force-directed layout algorithm with genetic algorithm techniques for biological graphs whose vertices have enzyme commission attributes

Download

index.pdf

Date

2019

Author

Aksoydan, Fırat

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

257
views

129
downloads

A pathway can be visualized as a graph whose layout is drawn by a force-directed algorithm. In our previous study, we have described EClerize which is a customized and improved Kamada Kawai force-directed algorithm in order to visualize pathways that contain nodes with attributes as EC numbers. EClerize creates clusters of vertices with enzymes that belong to the same EC class. Here, we make use of genetic algorithm (GA) to obtain a global optimum solution for EClerize and we integrate undirected graph layout drawing with GA. To provide diversity, 5 techniques in mutation phase and for crossover 2 techniques are employed. In mutation, vertices of a selected graph are moved randomly within a limited area or selected edges/vertices are exchanged according the routines of a technique. In crossover, the operation of exchanging vertices is performed between two selected graphs. In each iteration, fitness values of individuals are calculated by 6 different fitness measurements ranging from edge crossing number to drawing area. Overall relative fitness values are used to choose parent individuals. We have applied this method to 3 pathways and the results are better than those of the base study.

Subject Keywords

Enzymes, Enzymes Nomenclature., Keywords: Graph Visualization, Clustering, Force-directed Algorithm, Enzyme Commission Numbers, Genetic Algorithm.

URI

http://etd.lib.metu.edu.tr/upload/12623871/index.pdf
https://hdl.handle.net/11511/44463

Collections

Graduate School of Natural and Applied Sciences, Thesis

Suggestions

OpenMETU
Core

A Customized force-directed layout algorithm for biological graphs whose vertices have enzyme commission attributes Danacı, Hasan Fehmi; Atalay, Mehmet Volkan; Department of Computer Engineering (2015) Force directed layout algorithm is popularly used to draw biological graphs. However, it employs only graph structure. When we would like to embed domain-specific knowledge, such as biological or chemical attributes related to the vertices, force directed layout algorithm should be modified. It is then important to draw more readable layouts for biologists without the dispose of aesthetically pleasing way that comes from force-directed algorithm’s nature. This thesis aims to describe a modified and improved...
A Layout algorithm for visualization of graph alignments Akarsu, Andaç; Can, Tolga; Department of Computer Engineering (2017) Graph layout algorithms are commonly used when visualizing. Usually these algorithms focus on a single graph. To be able to visualize multiple graphs at once, such as the results of graph alignment algorithms on biological networks, new layout algorithms need to be developed. A layout algorithm for visualizing graph alignments should display the aligned graphs separately, so that both the graphs and their alignment can be viewed individually. In addition, for better interpretation of the alignment results, ...
The Floyd-Warshall all-pairs shortest paths algorithm for disconnected and very sparse graphs Toroslu, İsmail Hakkı (2023-01-01) The Floyd-Warshall algorithm is the most popular algorithm for determining the shortest paths between all vertex pairs in a graph. It is a very simple and an elegant algorithm. However, for graphs without any negative weighted edges, using Dijkstra's shortest path algorithm for every vertex as a source vertex to produce all-pairs shortest paths works significantly better than the Floyd-Warshall algorithm, especially for large graphs. Furthermore, for graphs with negative weighted edges, with no negative cyc...
A Buffer Zone Computation Algorithm for Corridor Rendering in GIS Er, Emre; Kilinc, Ismail; Gezici, Goerkem; Baykal, Buyurman (2009-09-16) This work defines a corridor rendering algorithm with variable leg buffer distances and the algorithm also supports geographic world model. A corridor is defined by a path and two distances for each leg to make a buffered zone around the path. Rendering of a corridor is a challenging task in GIS applications. Corridor is extensively used on mission computer displays on command and control platforms and civilian air control centers. Line buffering [1] and offset curve [2] approximations are the special case ...
A NOVEL PARTITIONING METHOD FOR ACCELERATING THE BLOCK CIMMINO ALGORITHM Torun, F. Sukru; Manguoğlu, Murat; Aykanat, Cevdet (2018-01-01) We propose a novel block-row partitioning method in order to improve the convergence rate of the block Cimmino algorithm for solving general sparse linear systems of equations. The convergence rate of the block Cimmino algorithm depends on the orthogonality among the block rows obtained by the partitioning method. The proposed method takes numerical orthogonality among block rows into account by proposing a row inner-product graph model of the coefficient matrix. In the graph partitioning formulation define...

Citation Formats

F. Aksoydan, “A Customized force-directed layout algorithm with genetic algorithm techniques for biological graphs whose vertices have enzyme commission attributes,” Thesis (M.S.) -- Graduate School of Natural and Applied Sciences. Computer Engineering., Middle East Technical University, 2019.