Though the TNM (Tumor, Lymph Node, Metastasis) is a widely used staging system for predicting the outcome of cancer patients, it is limited in prediction mainly because it does not integrate multiple prognostic factors. Expanding the TNM now becomes possible due to availability of large cancer patient datasets. In this paper, we introduce a group testing algorithm that can be used to add new prognostic factors while preserving the TNM staging system. Our approach starts with survival and evaluates its relation to potential prognostic factors individually and in various combinations. A demonstration is given for lung cancer.

Accurate prediction of survival rates of cancer patients is often key to stratify patients for prognosis and treatment. Survival prediction is often accomplished by the TNM system that involves only three factors: tumor extent, lymph node involvement, and metastasis. This prediction from the TNM has been limited, mainly because other potential prognostic factors are not used in the system. Based on availability of large cancer datasets, it is possible to establish powerful prediction systems by using machine learning procedures and statistical methods. In this paper, we present a clustering based approach to develop prognostic systems of cancer patients. Our method starts with grouping combinations that are formed using levels of factors recorded in the data. The dissimilarity measure between combinations is obtained through a sequence of data partitions produced by multiple clusterings. This dissimilarity measure is then used with a hierarchical clustering method in order to find clusters of combinations. Prediction of survival is made simply by using the survival function derived from each cluster. Our approach admits multiple factors and provides a practical and useful tool in outcome prediction of cancer patients. A demonstration of use of the proposed method is given for lung cancer patients.

This paper studies the algorithmic issues of the spanning star forest problem. We prove the following results: (1) There is a polynomial-time approximation scheme for planar graphs; (2) there is a polynomial-time $\frac{3}{5}$-approximation algorithm for graphs; (3) it is NP-hard to approximate the problem within ratio $\frac{259}{260} + \epsilon$ for graphs; (4) there is a linear-time algorithm to compute the maximum star forest of a weighted tree; (5) there is a polynomial-time $\frac{1}{2}$-approximation algorithm for weighted graphs. We also show how to apply this spanning star forest model to aligning multiple genomic sequences over a tandem duplication region.

The TNM (tumor, lymph node, metastasis) is a widely used staging system for predicting the outcome of cancer patients. However, the TNM is not accurate in prediction, partially due to the fact of deficient staging within and between stages. Based on the availability of large cancer patient datasets, there is a need to expand the TNM. In this paper, we present a general clustering-based approach to accomplish this task of expansion. This approach admits multiple factors. One major advantage of the approach is that patients within each generated group are homogeneous in terms of survival, so that a more accurate prediction of outcome of patients can be made. A demonstration of use of the proposed method is given for breast cancer patients.

A tournamentT n is an orientation of a complete graph on n vertices. A king in a tournament is a vertex from which every other vertex is reachable by a path of length at most 2. A sorted sequence of kings in a tournament T n is an ordered list of its vertices u 1 , u 2 , . . ., u n such that u i dominates $u_{i+1}$ ($u_i \rightarrow u_{i+1}$) and $u_i$ is a king in the subtournament induced by $\{u_j: i \le j \le n\}$ for each i=1,2, . . .,n-1. In particular, if T n is transitive, searching for a sorted sequence of kings in T n is equivalent to sorting a set of n numbers. In this paper, we try to find a sorted sequence of kings in a general tournament by asking the following type of binary question: "What is the orientation of the edge between two specified vertices u, v?" The cost for finding a sorted sequence of kings is the minimum number of binary questions asked in order to guarantee the finding of a sorted sequence of kings. Using an adversary argument proposed in this paper, we showthat the cost for finding a sorted sequence of kings in T n is $\Theta(n^{3/2})$ in the worst case, thus settling the order of magnitude of this question. We also show that the cost for finding a king in T n is $\Omega(n^{4/3})$ and O(n 3/2 ) in the worst case. Finally, we show a connection between a sorted sequence of kings and a median order in a tournament.

A shortest-path routing is optimal if it maximizes the probability of reaching the destination from a given source, assuming that each link in the system has a given failure probability. An approximation for the shortest-path routing policy, maximum-shortest-path (MSP) routing was proposed by Wu (see ibid., vol.48, no.3, p.247-55, 1999). Wu shows that: MSP is optimal in the mesh and hypercube networks; MSP is at least suboptimal in the torus network; MSP is optimal for 6 /spl times/ 6 and 8 /spl times/ 8 tori; and conjectured that MSP is optimal for 2-D tori in general. This short paper shows that, contrary to the claims by Wu, MSP is not optimal for a general N /spl times/ N torus-specifically, MSP is not optimal for a 12 /spl times/ 12 torus, and its optimal routing depends on the success probability.

Role assignments, introduced by Everett and Borgatti [2], who called them role colorings, formalize the idea, arising in the theory of social networks, that individuals of the same social role will relate in the same way to the individuals playing counterpart roles. If 𝒢 is a graph, a k-role assignment is a function r mapping the vertex set onto the set of integers {1,2, … , k} so that if r(x) =r(y) then the sets of roles assigned to the neighbors of x and y are the same. We ask how hard it is to determine if a graph has a 2-role assignment and show that recognizing if a graph has a 2-role assignment is NP-complete. © 2001 John Wiley & Sons, Inc.

R. Libeskind-Hadas (1998) provided a tight lower bound on the number of channels required by a broad class of deadlock-free wormhole routing algorithms. In this paper, we show a simpler proof of the tight lower bound.