Tez Arşivi

Tez aramanızı kolaylaştıracak arama motoru. Yazar, danışman, başlık ve özetlere göre tezleri arayabilirsiniz.


Orta Doğu Teknik Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Anabilim Dalı

2017

A layout algorithm for visualization of graph alignments

Çizge hizalama için çizge görselleme algoritması

Bu tez, YÖK tez merkezinde bulunmaktadır. Teze erişmek için tıklayın. Eğer tez bulunamazsa, YÖK Tez Merkezi'ndeki tarama bölümünde tez numarasını arayabilirsiniz. Tez numarası: 463607

Tezi Bul
Özet:

Çizge yerleşim algoritmaları çizgeleri ve ağları görselleme için yaygın olarak kullanılır. Genellikle bu algoritmalar tek bir çizge üzerine odaklanır. Birden fazla çizgeyi tek seferde görselleyebilme için, biyolojik ağlar üzerinde uygulanan çizge hizalama algoritmalarının sonuçları gibi, yeni yerleşim algoritmaları geliştirilmelidir. Çizge hizalama görsellemesi için kullanılacak yerleşim algoritması, hizalanan çizgeleri birbirinden ayrı olarak göstermelidir ki, çizgeler ve hizalamaları bireysel olarak görüntülenebilsin. Ayrıca, hizalama sonuçlarının daha iyi yorumu için, tek bir çizge görselleme algoritmalarına benzer olarak, kenar kesişmesi küçültülmeli ve yoğun olarak birbirine bağlı düğüm alt kümeleri bir arada gruplanmalıdır. Bu tezde, hizalanmış iki çizgenin görselleştirilmesi için bir çizge yerleşim sezgisi öneriyoruz. Hizalanmış düğümlerin listesi, düğüm benzerliklerine göre sıralanarak, çizge hizalama algoritmasından girdi olarak alınır. Düğümler minimum doğrusal düzenleme çözümünden adapte edilen bir yaklaşım kullanılarak yeniden sıralanır. Düğümler sonrasında dereceleri kullanılarak yerleştirilir. Önerilen yerleşim algoritması biyolojik ağlar üzerinde uygulanır ve elde edilen yerleşimler, yerleşim algoritması değerlendirmede standard bir kriteri olan kenar kesişimleri sayısı kullanılarak kalite için değerlendirilir. Sonuçlarımız önerilen algoritmanın çizge hizalama görselleştirirken standard yerleşim algoritmalarına kıyasla daha iyi performans sergilediğini gösterir.

Summary:

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, similar to single graph layout algorithms, edge crossings should be minimized and highly connected subsets of nodes should be grouped together. In this thesis, we propose a graph layout heuristic for visualization of alignments of two graphs. The list of aligned nodes, ordered with respect to node similarity, is taken as input from the graph alignment algorithm. The nodes are re-ordered using an approach adapted from a solution to the minimum linear arrangement problem. The nodes are then placed using their degrees. The proposed layout algorithm is applied on biological networks and the resulting layouts are assessed for quality using the number of edge crosses, a standard measure for evaluating layout algorithms. Our results show that the proposed algorithm performs better for graph alignment visualization compared to standard layout algorithms.