On the Linear-Cost Subtree-Transfer Distance between Phylogenetic Trees

Different phylogenetic trees for the same group of species are often produced either by procedures that use diverse optimality criteria [16] or from different genes [12] in the study of molecular evolution. Comparing these trees to find their similarities and dissimilarities (i.e., distance ) is thus an important issue in computational molecular biology. Several distance metrics including the nearest neighbor interchange (nni) distance and the subtree-transfer distance have been proposed and extensively studied in the literature. This article considers a natural extension of the subtree-transfer distance, called the linear-cost subtree-transfer distance, and studies the complexity and efficient approximation algorithms for this distance as well as its relationship to the nni distance. The linear-cost subtree-transfer model seems more suitable than the (unit-cost) subtree-transfer model in some applications. The following is a list of our results: 1. The linear-cost subtree-transfer distance is in fact identical to the nni distance on unweighted phylogenies. 2. There is an algorithm to compute an optimal linear-cost subtree-transfer sequence between unweighted phylogenies in O(n ⋅ 2 ^O(d) ) time, where d denotes the linear-cost subtree-transfer distance. Such an algorithm is useful when d is small. 3. Computing the linear-cost subtree-transfer distance between two weighted phylogenetic trees is NP-hard, provided we allow multiple leaves of a tree to share the same label (i.e., the trees are not necessarily uniquely labeled). 4. There is an efficient approximation algorithm for computing the linear-cost subtree-transfer distance between weighted phylogenies with performance ratio 2 . Received May 8, 1997; revised February 20, 1998.     

Local noncuppability in R/M

Given any [c],[a],[d]∈R/M such that [d]≤[a]≤[c], [a] is locally noncuppable between [c] and [d] if [d]<[a]≤[c]and [a] ∨ [b] < [c] for any [b]∈R/M such that [d]≤ [ b ] < [ c ]. It will be shown that given any nonzero [ c ] ∈ R/M, there are [ a ], [ d ] ∈R/M such that [d]<[a]≤[c] and[a] is locally noncuppable between [c] and[d].     

Polynomial Time Introreducibility

Abstract. We introduce the polynomial time version, in short ≤ ^P _T -introreducibility, of the notion of introreducibility studied in Recursion Theory. We give a simpler proof of the known fact that a set is ≤ ^P _T -introreducible if and only if it is in P. Our proof generalizes to virtually all the computation bounded reducibilities ≤ _r , showing that a set is ≤ _r -introreducible if and only if it belongs to the minimum ≤ _r -degree. It also holds for most unbounded reducibilities like ≤ _m , ≤ _c , ≤ _d , ≤ _p , ≤ _tt , etc., but it does not hold for ≤ _T . A very strong way for a set L to fail being ≤ _r -introreducible is that L is not ≤ _r -reducible to any coinfinite subset of L . We call such sets ≤ _r -introimmune. It is known that ≤ _T -introimmune sets exist but they are not arithmetical. In this paper we ask for which reducibilities ≤ _r there exist arithmetical ≤ _r -introimmune sets. We show that they exist for the reducibilities ≤ _c and ≤ ^N _m . Finally, we prove separation results between introimmunities.     

A General Deterministic Sequence for Sampling <Emphasis Type="Italic">d</Emphasis>-Dimensional Configuration Spaces

Previous works have already demonstrated that deterministic sampling can be competitive with respect to probabilistic sampling in sampling-based path planners. Nevertheless, the definition of a general sampling sequence for any d-dimensional configuration space satisfying the requirements needed for path planning is not a trivial issue. This paper makes a proposal of a simple and yet efficient deterministic sampling sequence based on the recursive use, over a multi-grid cell decomposition, of the ordering of the 2 ^d descendant cells of any parent cell. This ordering is generated by the digital construction method using a d×d matrix T _d . A general expression of this matrix (i.e. for any d) is introduced and its performance analyzed in terms of the mutual distance. The paper ends with a performance evaluation of the use of the proposed deterministic sampling sequence in different well known path planners. This work was partially supported by the CICYT projects DPI2004-03104 and DPI2005-00112. M. Roa is supported by Alβan (European Union Programme of High Level Scholarships for Latin America) under Scholarship No. E04D039103CO.     

On the number of transitive digraphs withn labeled vertices andk arcs

A computer determination of the numberT _n,k of transitive digraphs onn labeled vertices andk arcs is obtained for 2≤n≤6,0 ≤k≤n ²-n. Furthermore some formulae are given for determiningT _n,k, ∇n for extremal values ofk (namely, 0≤k≤6 andn ² -3n+4≤k≤n ²-n). Work carried out at Fondazione Ugo Bordoni under the agreements between Fondazione Ugo Bordoni and the Istituto Superiore P. T.     

The Complexity of Finding SUBSEQ(<Emphasis Type="Italic">A</Emphasis>)

Higman showed that if A is any language then SUBSEQ(A) is regular. His proof was nonconstructive. We show that the result cannot be made constructive. In particular we show that if f takes as input an index e of a total Turing Machine M _e , and outputs a DFA for SUBSEQ(L(M _e )), then ∅″≤_T f (f is Σ ₂-hard). We also study the complexity of going from A to SUBSEQ(A) for several representations of A and SUBSEQ(A).     

Efficient Parallel Computation of the Characteristic Polynomial of a Sparse, Separable Matrix

{This paper is concerned with the problem of computing the characteristic polynomial of a matrix. In a large number of applications, the matrices are symmetric and sparse : with O(n) non-zero entries. The problem has an efficient sequential solution in this case, requiring O(n ² ) work by use of the sparse Lanczos method. A major remaining open question is: to find a polylog time parallel algorithm with matching work bounds. Unfortunately, the sparse Lanczos method cannot be parallelized to faster than time Ω (n) using n processors. Let M(n) be the processor bound to multiply two n \times n matrices in O(log n) parallel time. Giesbrecht [G2] gave the best previous polylog time parallel algorithms for the characteristic polynomial of a dense matrix with O (M(n)) processors. There is no known improvement to this processor bound in the case where the matrix is sparse. Often, in addition to being symmetric and sparse, the matrix has a sparsity graph (which has edges between indices of the matrix with non-zero entries) that has small separators. This paper gives a new algorithm for computing the characteristic polynomial of a sparse symmetric matrix, assuming that the sparsity graph is s(n) -separable and has a separator of size s(n)=O(n ^γ ) , for some γ , 0 < γ < 1 , that when deleted results in connected components of ≤α n vertices, for some 0 < α < 1 , with the same property. We derive an interesting algebraic version of Nested Dissection, which constructs a sparse factorization of the matrix A-λ I _n where A is the input matrix and I _n is the n \times n identity matrix. While Nested Dissection is commonly used to minimize the fill-in in the solution of sparse linear systems, our innovation is to use the separator structure to bound also the work for manipulation of rational functions in the recursively factored matrices. The matrix elements are assumed to be over an arbitrary field. We compute the characteristic polynomial of a sparse symmetric matrix in polylog time using P(n)(n+M(s(n))) ≤ P(n)(n+ s(n) ^2.376 ) processors, where P(n) is the processor bound to multiply two degree n polynomials in O(log n) parallel time using a PRAM (P(n) = O(n) if the field supports an FFT of size n but is otherwise O(nlog log n) [CK]. Our method requires only that a matrix be symmetric and non-singular (it need not be positive definite as usual for Nested Dissection techniques). For the frequently occurring case where the matrix has small separator size, our polylog parallel algorithm has work bounds competitive with the best known sequential algorithms (i.e., the Ω(n ² ) work of sparse Lanczos methods), for example, when the sparsity graph is a planar graph, s(n) ≤ O( \sqrt n ) , and we require polylog time with only P(n)n ^1.188 processors. } Received September 26, 1997; revised June 5, 1999.     

Approximating Shortest Paths on Weighted Polyhedral Surfaces

One common problem in computational geometry is that of computing shortest paths between two points in a constrained domain. In the context of Geographical Information Systems (GIS), terrains are often modeled as Triangular Irregular Networks (TIN) which are a special class on non-convex polyhedra. It is often necessary to compute shortest paths on the TIN surface which takes into account various weights according to the terrain features. We have developed algorithms to compute approximations of shortest paths on non-convex polyhedra in both the unweighted and weighted domain. The algorithms are based on placing Steiner points along the TIN edges and then creating a graph in which we apply Dijkstra's shortest path algorithm. For two points s and t on a non-convex polyhedral surface P , our analysis bounds the approximate weighted shortest path cost as || Π'(s,t)|| ≤ ||Π(s,t)|| + W |L| , where L denotes the longest edge length of \cal P and W denotes the largest weight of any face of P . The worst case time complexity is bounded by O(n ⁵ ) . An alternate algorithm, based on geometric spanners, is also provided and it ensures that ||Π' (s,t)|| ≤β(||Π(s,t)|| + W|L|) for some fixed constant β >1 , and it runs in O(n ³ log n) worst case time. We also present detailed experimental results which show that the algorithms perform much better in practice and the accuracy is near-optimal. Received April 15, 1998; revised February 15, 1999.     

A robust model for finding optimal evolutionary trees

Constructing evolutionary trees for species sets is a fundamental problem in computational biology. One of the standard models assumes the ability to compute distances between every pair of species, and seeks to find an edge-weighted treeT in which the distanced _ij ^T in the tree between the leaves ofT corresponding to the speciesi andj exactly equals the observed distance,d _ij . When such a tree exists, this is expressed in the biological literature by saying that the distance function or matrix isadditive, and trees can be constructed from additive distance matrices in0(n ²) time. Real distance data is hardly ever additive, and we therefore need ways of modeling the problem of finding the best-fit tree as an optimization problem.In this paper we present several natural and realistic ways of modeling the inaccuracies in the distance data. In one model we assume that we have upper and lower bounds for the distances between pairs of species and try to find an additive distance matrix between these bounds. In a second model we are given a partial matrix and asked to find if we can fill in the unspecified entries in order to make the entire matrix additive. For both of these models we also consider a more restrictive problem of finding a matrix that fits a tree which is not only additive but alsoultrametric. Ultrametric matrices correspond to trees which can be rooted so that the distance from the root to any leaf is the same. Ultrametric matrices are desirable in biology since the edge weights then indicate evolutionary time. We give polynomial-time algorithms for some of the problems while showing others to be NP-complete. We also consider various ways of fitting a given distance matrix (or a pair of upper- and lower-bound matrices) to a tree in order to minimize various criteria of error in the fit. For most criteria this optimization problem turns out to be NP-hard, while we do get polynomial-time algorithms for some.Supported by DIMACS under NSF Contract STC-88-09648.Supported by NSF Grant CCR-9108969.This work was begun while this author was visiting DIMACS in July and August 1992, and was supported in part by the U.S. Department of Energy under Contract DE-AC04-76DP00789.     

Note on the Structure of Kruskal’s Algorithm

We study the merging process when Kruskal’s algorithm is run with random graphs as inputs. Our aim is to analyze this process when the underlying graph is the complete graph on n vertices lying in [0,1] ^d , and edge set weighted with the Euclidean distance. The height of the binary tree explaining the merging process is proved to be Θ(n) on average. On the way to the proof, we obtain similar results for the complete graph and the d-dimensional square lattice with i.i.d. edge weights.     

A new quantum claw-finding algorithm for three functions

Fork functionsf ₁, ...f _k, ak-tuple (x ₁, ...x _k) such thatf ₁(x ₁)=...=f _k(x _k) is called a claw off ₁, ...,f _k. In this paper, we construct a new quantum claw-finding algorithm for three functions that is efficient when the numberM of intermediate solutions is small. The known quantum claw-finding algorithm for three functions requiresO(N ^7/8 logN) queries to find a claw, but our algorithm requiresO(N ^3/4 logN) queries ifM ≤ √N andO(N ^7/12 M ^1/3 logN) queries otherwise. Thus, our algorithm is more efficient ifM≤N ^7/8. Kazuo Iwama, Ph.D.: Professor of Informatics, Kyoto University, Kyoto 606-8501, Japan. Received BE, ME, and Ph.D. degrees in Electrical Engineering from Kyoto University in 1978, 1980 and 1985, respectively. His research interests include algorithms, complexity theory and quantum computation. Editorial board of Information Processing Letters and Parallel Computing. Council Member of European Association for Theoretical Computer Science (EATCS). Akinori Kawachi: Received B.Eng. and M.Info. from Kyoto University in 2000 and 2002, respectively. His research interests are quantum computation and distributed computation.     

Geometric Representation of Graphs in Low Dimension Using Axis Parallel Boxes

An axis-parallel k-dimensional box is a Cartesian product R ₁×R ₂×???×R _k where R _i (for 1≤i≤k) is a closed interval of the form [a _i ,b _i ] on the real line. For a graph G, its boxicity box?(G) is the minimum dimension k, such that G is representable as the intersection graph of (axis-parallel) boxes in k-dimensional space. The concept of boxicity finds applications in various areas such as ecology, operations research etc. A number of NP-hard problems are either polynomial time solvable or have much better approximation ratio on low boxicity graphs. For example, the max-clique problem is polynomial time solvable on bounded boxicity graphs and the maximum independent set problem for boxicity d graphs, given a box representation, has a $\lfloor 1+\frac{1}{c}\log n\rfloor^{d-1}An axis-parallel k-dimensional box is a Cartesian product R ₁×R ₂×⋅⋅⋅×R _k where R _i (for 1≤i≤k) is a closed interval of the form [a _i ,b _i ] on the real line. For a graph G, its boxicity box (G) is the minimum dimension k, such that G is representable as the intersection graph of (axis-parallel) boxes in k-dimensional space. The concept of boxicity finds applications in various areas such as ecology, operations research etc. A number of NP-hard problems are either polynomial time solvable or have much better approximation ratio on low boxicity graphs. For example, the max-clique problem is polynomial time solvable on bounded boxicity graphs and the maximum independent set problem for boxicity d graphs, given a box representation, has a ?1+\frac1clogn?^d-1\lfloor 1+\frac{1}{c}\log n\rfloor^{d-1} approximation ratio for any constant c≥1 when d≥2. In most cases, the first step usually is computing a low dimensional box representation of the given graph. Deciding whether the boxicity of a graph is at most 2 itself is NP-hard.     

Mapping Between 2-D Meshes of the Same Size

1IntroductionInrece11tyears,n1a11yparallelalgoritlImshavebeendesignedtosolvedifferentproblemso1lvario1ls11etworktopologics.Bi11arytrees,meshesandhypercubesarethethreeimportal1tl1etworktop()logieswllicllhaterpcoivedintensivestlldy.WiththeadvanceofVLSI,manyllewl1etworkssuchasstargrapl1[1]havebeenorwiIlbeintroduced.Inor相似文献   

Learning Matrix Functions over Rings

Let R be a commutative Artinian ring with identity and let X be a finite subset of R . We present an exact learning algorithm with a polynomial query complexity for the class of functions representable as f(x) = Π _i=1 ⁿ A _i (x _i ), where, for each 1 ≤ i ≤ n , A _i is a mapping A _i : X → R ^{mi× mi+1} and m ₁ = m _n+1 = 1 . We show that the above algorithm implies the following results: 1. Multivariate polynomials over a finite commutative ring with identity are learnable using equivalence and substitution queries. 2. Bounded degree multivariate polynomials over Z _n can be interpolated using substitution queries. 3. The class of constant depth circuits that consist of bounded fan-in MOD gates, where the modulus are prime powers of some fixed prime, is learnable using equivalence and substitution queries. Our approach uses a decision tree representation for the hypothesis class which takes advantage of linear dependencies. This paper generalizes the learning algorithm for automata over fields given in [BBB+]. Received January 28, 1997; revised May 29, 1997, June 18, 1997, and June 26, 1997.     

Thermodynamics of regular cosmological black holes with de Sitter interior

We address the question of thermodynamics of a regular spherically symmetric cosmological black hole. The spacetime is asymptotically de Sitter as r → 0 and as r → ∞. A source termin the Einstein equations connects smoothly two de Sitter vacua with different values of the cosmological constant and corresponds to an anisotropic vacuum fluid defined by the symmetry of its stress-energy tensor, invariance under radial boosts. In the range of the mass parameter M _crit1 ≤ M ≤ M _crit2 it describes a regular cosmological black hole.     

Linear Time Algorithms for Generalized Edge Dominating Set Problems

We prove that a generalization of the edge dominating set problem, in which each edge e needs to be covered b _e times for all e∈E, admits a linear time 2-approximation for general unweighted graphs and that it can be solved optimally for weighted trees. We show how to solve it optimally in linear time for unweighted trees and for weighted trees in which b _e ∈{0,1} for all e∈E. Moreover, we show that it solves generalizations of weighted matching, vertex cover, and edge cover in trees.     

<Emphasis Type="Italic">f</Emphasis>-Sensitivity Distance Oracles and Routing Schemes

An f-sensitivity distance oracle for a weighted undirected graph G(V,E) is a data structure capable of answering restricted distance queries between vertex pairs, i.e., calculating distances on a subgraph avoiding some forbidden edges. This paper presents an efficiently constructible f-sensitivity distance oracle that given a triplet (s,t,F), where s and t are vertices and F is a set of forbidden edges such that |F|≤f, returns an estimate of the distance between s and t in G(V,E∖F). For an integer parameter k≥1, the size of the data structure is O(fkn ^1+1/k log (nW)), where W is the heaviest edge in G, the stretch (approximation ratio) of the returned distance is (8k−2)(f+1), and the query time is O(|F|⋅log ² n⋅log log n⋅log log d), where d is the distance between s and t in G(V,E∖F).     

<Emphasis Type="Italic">k</Emphasis>-Nearest-Neighbor Clustering and Percolation Theory

Let P be a realization of a homogeneous Poisson point process in ℝ ^d with density 1. We prove that there exists a constant k _d , 1<k _d <∞, such that the k-nearest neighborhood graph of P has an infinite connected component with probability 1 when k≥k _d . In particular, we prove that k ₂≤213. Our analysis establishes and exploits a close connection between the k-nearest neighborhood graphs of a Poisson point set and classical percolation theory. We give simulation results which suggest k ₂=3. We also obtain similar results for finite random point sets. Part of the work was done while S.-H. Teng was at Xerox Palo Alto Research Center and MIT. The work of F.F. Yao was supported in part by a grant from the Research Grants Council of the Hong Kong Special Administrative Region, China [Project No. CityU 1165/04E].     

Labeling Schemes for Tree Representation

This paper deals with compact label-based representations for trees. Consider an n-node undirected connected graph G with a predefined numbering on the ports of each node. The all-ports tree labeling ℒ _all gives each node v of G a label containing the port numbers of all the tree edges incident to v. The upward tree labeling ℒ _up labels each node v by the number of the port leading from v to its parent in the tree. Our measure of interest is the worst case and total length of the labels used by the scheme, denoted M _up (T) and S _up (T) for ℒ _up and M _all (T) and S _all (T) for ℒ _all . The problem studied in this paper is the following: Given a graph G and a predefined port labeling for it, with the ports of each node v numbered by 0,…,deg (v)−1, select a rooted spanning tree for G minimizing (one of) these measures. We show that the problem is polynomial for M _up (T), S _up (T) and S _all (T) but NP-hard for M _all (T) (even for 3-regular planar graphs). We show that for every graph G and port labeling there exists a spanning tree T for which S _up (T)=O(nlog log n). We give a tight bound of O(n) in the cases of complete graphs with arbitrary labeling and arbitrary graphs with symmetric port labeling. We conclude by discussing some applications for our tree representation schemes. A preliminary version of this paper has appeared in the proceedings of the 7th International Workshop on Distributed Computing (IWDC), Kharagpur, India, December 27–30, 2005, as part of Cohen, R. et al.: Labeling schemes for tree representation. In: Proceedings of 7th International Workshop on Distributed Computing (IWDC), Lecture Notes of Computer Science, vol. 3741, pp. 13–24 (2005). R. Cohen supported by the Pacific Theaters Foundation. P. Fraigniaud and D. Ilcinkas supported by the project “PairAPair” of the ACI Masses de Données, the project “Fragile” of the ACI Sécurité et Informatique, and by the project “Grand Large” of INRIA. A. Korman supported in part by an Aly Kaufman fellowship. D. Peleg supported in part by a grant from the Israel Science Foundation.     

A Good Oracle Is Hard to Beat

A well-known result of Sacks [24] states that if A is nonrecursive, then the set {B : A ≤ _T B} has measure zero. Thus, from a measure-theoretic perspective, a ``good' (i.e., nonrecursive) oracle is hard to beat in the partial order of Turing degrees. We show that analogous results hold for the standard notions of inductive inference, as well as for the notions of approximate inference. Received January 25, 1997; revised March 10, 1997, June 3, 1997, and June 15, 1997.