Algorithms for the analysis and visualization of biomedical networks

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 lling visualization for DAGs. Space lling 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 rst transforming the DAG into a tree. However this transformation has several undesirable e ects 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 lling techniques without converting it into a tree rst. We de ne drawing constraints that generalize treemaps to space lling 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 de ne 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 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 the interval (0; 1] and are interpreted as strength of dependence. We call these networks greyscale since they can be visualized with di erent 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 rst case study compares brain functional networks of alcoholic and control subjects during memory rehearsal tasks and shows that there are statistically signi cant di erences 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 di erentiate between the two imagery tasks using network statistics.