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

---

Tezin Türü: Yüksek Lisans

Tezin Yürütüldüğü Kurum: Orta Doğu Teknik Üniversitesi, Fen Bilimleri Enstitüsü, Türkiye

Tezin Onay Tarihi: 2019

Tezin Dili: İngilizce

Öğrenci: FIRAT AKSOYDAN

Danışman: Mehmet Volkan Atalay

Özet:

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.