Probabilistic fault diagnosis of clustered faults for multiprocessor systems

With the development of high-performance computing and the expansion of large-scale multiprocessor sys-tems,it is significant to study the reliability of systems.Probabilistic fault diagnosis is of practical value to the reliabilityanalysis of multiprocessor systems.In this paper,we design a linear time diagnosis algorithm with the multiprocessor sys-tem whose threshold is set to 3,where the probability that any node is correctly diagnosed in the discrete state can be cal-culated.Furthermore,we give the probabilities that all nodes of a d-regular and d-connected graph can be correctly diag-nosed in the continuous state under the Weibull fault distribution and the Chi-square fault distribution.We prove thatthey approach to 1,which implies that our diagnosis algorithm can correctly diagnose almost all nodes of the graph.

On the Probability of Generating a Primitive Matrix

Given a k×n integer primitive matrix A(i.e.,a matrix can be extended to an n×n unimodular matrix over the integers)with the maximal absolute value of entries‖A‖bounded by an integer λ from above,the authors study the probability that the m×n matrix extended from A by appending other m-k row vectors of dimension n with entries chosen randomly and independently from the uniform distribution over{0,1,…,λ-1}is still primitive.The authors present a complete and rigorous proof of a lower bound on the probability,which is at least a constant for fixed m in the range[k+1,n-4].As an application,the authors prove that there exists a fast Las Vegas algorithm that completes a k×n primitive matrix A to an n×n unimodular matrix within expected O(n^(ω)log‖A‖)bit operations,where O is big-O but without log factors,ω is the exponent on the arithmetic operations of matrix multiplication.

Algorithmic approaches to clonal reconstruction in heterogeneous cell populations

Background:The reconstruction of clonal haplotypes and their evolutionary history in evolving populations is a common problem in both microbial evolutionary biology and cancer biology.The clonal theory of evolution provides a theoretical framework for modeling the evolution of clones.Results:In this paper,we review the theoretical framework and assumptions over which the clonal reconstruction problem is formulated.We formally define the problem and then discuss the complexity and solution space of the problem.Various methods have been proposed to find the phylogeny that best explains the observed data.We categorize these methods based on the type of input data that they use(space-resolved or time-resolved),and also based on their computational formulation as either combinatorial or probabilistic.It is crucial to understand the different types of input data because each provides essential but distinct information for drastically reducing the solution space of the clonal reconstruction problem.Complementary information provided by single cell sequencing or from whole genome sequencing of randomly isolated clones can also improve the accuracy of clonal reconstruction.We briefly review the existing algorithms and their relationships.Finally we summarize the tools that are developed for either directly solving the clonal reconstruction problem or a related computational problem.Conclusions:In this review,we discuss the various formulations of the problem of inferring the clonal evolutionary history from allele frequeny data,review existing algorithms and catergorize them according to their problem formulation and solution approaches.We note that most of the available clonal inference algorithms were developed for elucidating tumor evolution whereas clonal reconstruction for unicellular genomes are less addressed.We conclude the review by discussing more open problems such as the lack of benchmark datasets and comparison of performance between available tools.