Wednesday, September 26, 2012

A fast layout algorithm for protein interaction networks

BIOINFORMATICS Vol. 19 no. 15 2003, pages 1882–1888 DOI: 10.1093/bioinformatics/btg346 A fast layout algorithm for protein interaction networks Kyungsook Han ∗ and Byong-Hyon Ju School of Computer Science & Engineering, Inha University, Inchon 402-751, Korea Received on May 1, 2003; revised and accepted on July 15, 2003 ABSTRACT Motivation: Graph drawing algorithms are often used for visualizing relational information, but a naive implementa- tion of a graph drawing algorithm encounters real difficulties when drawing large-scale graphs such as protein interaction

networks. Results: We have developed a new, extremely fast layout algorithm for visualizing large-scale protein interaction net- works in the three-dimensional space. The algorithm (1) first finds a layout of connected components of an entire net- work, (2) finds a global layout of nodes with respect to pivot nodes within a connected component and (3) refines the local layout of each connected component by first relocating midnodes with respect to their cutvertices and direct neigh- bors of the cutvertices and then by relocating all nodes with respect to their neighbors within distance 2. Advantages of this algorithm over classical graph drawing methods include: (1) it is an order of magnitude faster, (2) it can directly visual- ize data from protein interaction databases and (3) it provides several abstraction and comparison operations for effectively analyzing large-scale protein interaction networks. Availability: http://wilab.inha.ac.kr/interviewer/ Contact: khan@inha.ac.kr INTRODUCTION While traditional biochemical experiments had generated a small set of data for individual protein–protein interactions, the last three years have seen a rapid expansion of protein inter- action data due to the recent development of high-throughput interaction detection methods such as yeast two-hybrid (Ito et al., 2000) and mass spectrometry techniques. The inter- action data is available either in text files or in databases. However, due to the volume of data, a graphical representa- tion of protein interactions has proven to be much easier to understand than a long list of interacting proteins. Further- more, a network of protein interactions provides us with a clear notion of protein function by showing a context within which function can be interpreted. Protein–protein interactions are typically visualized as an undirected graph G = (V , E), where x, y ∈ V represent ∗ To whom correspondence should be addressed proteins and (x, y) ∈ E represents an interaction between proteins x and y. Visualization of a graph is straightforward when dealing with a small number of nodes and edges. In practice, protein–protein interaction networks often consist of thousands of nodes or more, which severely limit the usefulness of many graph drawing tools either because they produce cluttered drawings with many edge crossings or static drawings that are not easy to modify, they are too slow for interactive analysis with large data sets, or because they require input data to be in specific format rather than taking the data directly from protein–protein interaction databases. The ultimate usefulness of a protein interaction...

Website: bioinformatics.oxfordjournals.org | Filesize: -
No of Page(s): 7
Download A fast layout algorithm for protein interaction networks.pdf

No comments:

Post a Comment