BACKGROUND: Many research results show that the biological systems are composed of functional modules. Members in the same module usually have common functions. This is useful information to understand how biological systems work. Therefore, detecting functional modules is an important research topic in the post-genome era. One of functional module detecting methods is to find dense regions in Protein-Protein Interaction (PPI) networks. Most of current methods neglect confidence-scores of interactions, and pay little attention on using gene expression data to improve their results. RESULTS: In this paper, we propose a novel hub-attachment based method to detect functional modules from confidence-scored protein interactions and expression profiles, and we name it HUNTER. Our method not only can extract functional modules from a weighted PPI network, but also use gene expression data as optional input to increase the quality of outcomes. Using HUNTER on yeast data, we found it can discover more novel components related with RNA polymerase complex than those existed methods from yeast interactome. And these new components show the close relationship with polymerase after functional analysis on Gene Ontology. CONCLUSION: A C++ implementation of our prediction method, dataset and supplementary material are available at http://hub.iis.sinica.edu.tw/Hunter/. Our proposed HUNTER method has been applied on yeast data, and the empirical results show that our method can accurately identify functional modules. Such useful application derived from our algorithm can reconstruct the biological machinery, identify undiscovered components and decipher common sub-modules inside these complexes like RNA polymerases I, II, III.

Many researchers used computer technology over the last decade to build a virtual learning community in Web-based learning environment. However, building and managing a sustainable learning community remains challenging. One of the goals of this study is to try to identify some major events that affect learning community growth, and another goal is employ these events to develop a regression model for forecasting accumulated effective users in learning communities in the future. This study uses a Web-based learning system, as a preliminary analysis environment. Four major events that influence learning communities were identified, and these events were used to establish a regression model for calculating accumulated effective users. Future works will attempt to prove that the forecast regression model affects community building.

The purpose of this study is to develop a passport system based on ARCS model for Internet users to learn basic information technology skills. The system is designed to increase learners' motivation and use it actively. Due to an assistant teaming mechanism, it can improve learners' information literacy. The teaming contents are about information technologies. The styles of the test include multi-choices and practical manipulation tasks. The system automatically evaluates the results, records the process and outcome of the test. The system adopts a role-play strategy, so that users can proceed to the test in the form of games. When a user encounters problems in the test, he/she can find relevant information to assist his/her teaming. The main users of the system are teachers and students of junior high schools and elementary schools at Taoyuan County in Taiwan. From December 1999 to June 2001, 1273783 users have already used the system.

In this paper, we sketch common properties of a class of so-called subgraph optimization problems that can be systematically solved on distance-hereditary graphs. Based on the found properties, we then develop a general problem-solving paradigm that solves these problems efficiently in parallel. As a by-product, we also obtain new linear-time algorithms by a sequential simulation of our parallel algorithms. Let T d |V|,|E|) and P d (|V|,|E|) denote the time and processor complexities, respectively, required to construct a decomposition tree of a distance-hereditary graph G=(V,E) on a PRAM model M d . Based on the proposed paradigm, we show that the maximum independent set problem, the maximum clique problem, the vertex connectivity problem, the domination problem, and the independent domination problem can be sequentially solved in O(|V|+|E|) time, and solved in parallel in O(T d (|V|,|E|)+log |V|) time using O(P d (|V|,|E|)+|V|log |V|)processors on M d . By constructing a decomposition tree under a CREW PRAM, we also show that T d (|V|,|E|)=O(log 2 |V|) and P d (|V|,|E|)=O(|V|+|E|).

In this paper, we aim to embed longest fault-free paths in an n-dimensional star graph with edge faults. When n/spl ges/6 and there are n-3 edge faults, a longest fault-free path can be embedded between two arbitrary distinct vertices, exclusive of two exceptions in which at most two vertices are excluded. Since the star graph is regular of degree n-1, n-3 (edge faults) is maximal in the worst case. When n/spl ges/6 and there are n-4 edge faults, a longest fault-free path can be embedded between two arbitrary distinct vertices. The situation of n<6 is also discussed.

Suppose that G is a bipartite graph with its partite sets of equal size. G is said to be strongly Hamiltonian-laceable if there is a Hamiltonian path between every two vertices that belong to different partite sets and there is a path of (maximal) length N - 2 between every two vertices that belong to the same partite set, where N is the order of G. In other words, a strongly Hamiltonian-laceable graph has a longest path between every two of its vertices. In this paper, we show that the star graphs with dimension four or larger are strongly Hamiltonian-laceable. © 2000 john Wiley & Sons, Inc.

The arrangement graph A/sub n,k/, which is a generalization of the star graph (n-k=1), presents more flexibility than the star graph in adjusting the major design parameters: number of nodes, degree, and diameter. Previously, the arrangement graph has proved Hamiltonian. In this paper, we further show that the arrangement graph remains Hamiltonian even if it is faulty. Let |F/sub e/| and |F/sub v/| denote the numbers of edge faults and vertex faults, respectively. We show that A/sub n,k/ is Hamiltonian when 1) (k=2 and n-k/spl ges/4, or k/spl ges/3 and n-k/spl ges/4+[k/2]), and |F/sub e/|/spl les/k(n-k)-2, or 2) k/spl ges/2, n-k/spl ges/2+[k/2], and |F/sub e/|/spl les/k(n-k-3)-1, or 3) k/spl ges/2, n-k/spl ges/3, and |F/sub e/|/spl les/k, or 4) n-k/spl ges/3 and |F/sub v/|/spl les/n-3, or 5) n-k/spl ges/3 and |F/sub v/|+|F/sub e/|/spl les/k. Besides, for A/sub n,k/ with n-k=2, we construct a cycle of length at least 1) [n!/(n-k!)]-2 if |F/sub e/|/spl les/k-1, or 2) [n!/(n-k)!]-|F/sub v/|-2(k-1) if |F/sub v/|/spl les/k-1, or 3) [n!/(n-k)!]-|F/sub v/|-2(k-1) if |F/sub e/|+|F/sub v/|/spl les/k-1, where [n!/(n-k)!] is the number of nodes in A/sub n,k/.

In this paper, a network-partitioning approach for one-to-all broadcasting on wormhole-routed networks is proposed. To broadcast a message, the scheme works in three phases. First, a number of data-distributing networks (DDNs), which can work independently, are constructed. Then the message is evenly divided into submessages, each being sent to a representative node in one DDN. Second, the submessages are broadcast on the DDNs concurrently. Finally, a number of data-collecting networks (DCNs), which can work independently too, are constructed. Then, concurrently on each DCN, the submessages are collected and combined into the original message. Our approach, especially designed for wormhole-routed networks, is conceptually similar but fundamentally very different from the traditional approach of using multiple edge-disjoint spanning trees in parallel for broadcasting in store-and-forward networks. One interesting issue is on the definition of independent DDNs and DCNs, in the sense of wormhole routing. We show how to apply this approach to tori, meshes, and hypercubes. Thorough analyses and comparisons based on different system parameters and configurations are conducted. The results do confirm the advantage of our scheme, under various system parameters and conditions, over other existing broadcasting algorithms.

The star graph has been recognized as an attractive alternative to the hypercube. Let F/sub e/ and F/sub /spl nu// be the sets of vertex faults and edge faults, respectively. Previously, Tseng et al. showed that an n-dimensional star graph can embed a ring of length n! if |F/sub e/|/spl les/n-3 (|F/sub /spl nu//|=0), and a ring of length at least n!-4|F/sub /spl nu//| if |F/sub /spl nu//|/spl les/n-3 (|F/sub e/|=0). Since an n-dimensional star graph is regular of degree n-1 and is bipartite with two partite sets of equal size, our result achieves optimality in the worst case.

The arrangement graph A/sub n,k/, which is a generalization of the star graph (n-t=1), presents more flexibility than the star graph in adjusting the major design parameters: number of nodes, degree, and diameter. Previously the arrangement graph has proven hamiltonian. In this paper we further show that the arrangement graph remains hamiltonian even if it is faulty. Let |F/sub e/| and |F/sub v/| denote the numbers of edge faults and vertex faults, respectively. We show that A/sub n,k/ is hamiltonian when (1) (k=2 and n-k/spl ges/4, or k/spl ges/3 and n-k/spl ges/4+[k/2]), and |F/sub e/|/spl les/k(n-k-2)-1, or (2) k/spl ges/2, n-k/spl ges/2+[k/2], and |F/sub e/|/spl les/k(n-k-3)-1, or (3) k/spl ges/2, n-k/spl ges/3, and |F/sub 3/|/spl les/k.

We present efficient parallel algorithms for finding a minimum weighted connected dominating set, a minimum weighted Steiner tree for a distance-hereditary graph which take O(log n) time using O(n+m) processors on a CRCW PRAM, where n and m are the number of vertices and edges of a given graph, respectively. We also find a maximum weighted clique of a distance-hereditary graph in O(log/sup 2/ n) time using O(n+m) processors on a CREW PRAM.

A fast parallel algorithm, which is generalized from the parallel algorithms for solving banded linear systems, is proposed to solve sparse triangular systems. The original problem is transformed into a directed graph. The solving procedure then consists of eliminating edges in this graph. The worst-case time-complexity of this parallel algorithm is O(log/sup 2/n) where n is the size of the coefficient matrix. When the coefficient matrix is a triangular banded matrix with bandwidth m, then the time-complexity of the algorithm is O(log(m)*log(n)).>