Doctoral theses
Current Record: 93 of 121
|
|
| Identifier |
000355335 |
| Title |
Algorithms for the analysis and visualization of biomedical networks |
| Alternative Title |
Αλγόριθμοι για την ανάλυση και οπτικοποίηση βιοϊατρικών δικτύων |
|
Author
|
Τσιάρας, Βασίλειος Λεωνίδα
|
|
Thesis advisor
|
Τόλλης, Ιωάννης Γ
|
| Abstract |
Networks are prevalent in life sciences. Two characteristic examples are Gene
Ontology and brain functional networks.
Gene Ontology (GO) is structured as a Directed Acyclic Graph (DAG).
Motivated by the fact that visualizing the whole GO with node-link representation leads to an unintelligible image, we propose space filling visualization for DAGs. Space filling visualizations, such as the treemaps, have the capacity to display thousands of items legibly in limited space. Treemaps have been used to
visualize the GO by first transforming the DAG into a tree. However this transformation has several undesirable effects such as producing trees with a large number of nodes and scattering the rectangles associated with the duplicates of a node around the display rectangle. In this thesis we introduce the problem of visualizing a DAG with space filling techniques without converting it into a tree first. We define drawing constraints that generalize treemaps to space filling visualizations of DAGs which we call DAGmaps. Then we show that deciding whether or not a DAG admits a DAGmap drawing is NP-complete. For this reason we study two special cases of the problem and we propose a heuristic algorithm that reduces the vertex duplications. First, we define a special case of the problem called one-dimensional DAGmap where the initial rectangle is sliced in one-dimension (e.g. the vertical). We prove that a DAG admits a one-dimensional DAGmap if and only if it admits a directed ε-visibility representation.
This one-to-one correspondence between the two problems leads to
characterization of the class of DAGs that admit a one-dimensional DAGmap
as well as to elegant linear time decision and drawing algorithms. Another special case of the problem occurs when the input is restricted to Two Terminal Series Parallel (TTSP) digraphs. We show that every TTSP digraph admits a DAGmap which can be drawn using the decomposition tree of G in linear time. The heuristic algorithm that we propose decomposes a DAG into component st-graphs using dominance relationships and then combines the drawings of the
component st-graphs. In case that an st-graph does not admit a DAGmap then
it is transformed into a TTSP digraph via vertex duplications. This algorithm
performs fewer vertex duplications than the transformation of a DAG into a
tree when the DAG can be decomposed into component st-graphs. Finally we
implemented all the proposed algorithms in a program called DAGmap View. This program, which also implements the novel feature of separate layout and nesting functions, is an ideal tool to visualize and navigate through the GO.
Brain functional networks are modeled with valued graphs where the vertices
correspond to brain areas and the edges denote statistical dependence
between brain areas. The edge values belong to interval (0, 1] and are interpreted as strength of dependence. We call these networks greyscale since they can be visualized with different shades of grey. Motivated by the fact that a program that analyzes and visualizes brain functional networks is of interest to researchers working in brain connectivity, we created BrainNetVis. This program
displays greyscale networks and implements a number of measures, most of which were selected from the literature. However we also contributed to the development of the theory of greyscale networks by proposing: a) a function that converts edge strength into edge lengths; b) a formula that calculates the importance of a vertex due to its position on a network as well as due to its attributes and c) some generalizations of graph theoretic measures to greyscale networks. We demonstrate BrainNetVis through two case studies. The first case study compares brain functional networks of alcoholic and control subjects during memory rehearsal tasks and shows that there are statistically significant
differences between the two groups at beta band. The second case study compares brain functional networks of a healthy subject during two motor imagery tasks (left hand and foot). We found that the corresponding networks are very similar and we propose a method to differentiate between the two imagery tasks using network statistics.
|
| Language |
English |
| Issue date |
2009-10-07 |
| Collection
|
School/Department--School of Sciences and Engineering--Department of Computer Science--Doctoral theses
|
|
|
Type of Work--Doctoral theses
|
| Permanent Link |
https://elocus.lib.uoc.gr//dlib/3/b/0/metadata-dlib-b403b98150537167a1ec59e545c7e493_1275635648.tkl
|
| Views |
582 |
Collections
