The split-row problem (SR), introduced by Hajirasouliha and Raphael [WABI 2014], models an effective method for reconstructing a perfect phylogeny from mixed tumor samples. In this problem, an $m \times n$ binary matrix $M$ is given. A split-row operation on $M$ is defined as replacing a row $r$ by $k > 1$ rows whose bitwise OR is equal to $r$. The cost of the operation is the number of additional rows induced, that is, $k - 1$. The objective is to find a sequence of operations that transforms $M$ into a matrix corresponding to a perfect phylogeny and the total cost is minimized. Hujdurović et al. [TCBB 2018] proved the NP-hardness of SR. Let ${\rm{\varepsilon }}( M )$ denote the minimum total cost. In this paper, we show that SR admits a polynomial size kernel, which has at most $3{\rm{\varepsilon }}( M )$ rows and $4{\rm{\varepsilon }}( M ) - 1$ columns. Our kernelization algorithm requires $O( {\max ( {{{m}^{0.373}}{{n}^2}, m{{n}^{1.373}}} )} )$ time. When $\varepsilon ( M )$ is small, it can be used as a preprocessing procedure to speed up all previous exact algorithms for SR.

Consensus trees have been widely used in evolutionary studies to combine phylogenetic information of individual gene trees. This paper studies one of the most well-known consensus tree methods: the frequency difference consensus tree. Jansson et al. [IEEE/ACM TCBB, 2018] had an $O( {\text{min}}\{ {{{k}^2}n,\ k{{n}^2}} \} + kn\ \mathrm{l}{{\mathrm{g}}^2}n )$-time algorithm for constructing the frequency difference consensus tree of k phylogenetic trees on the same set of n taxa. Later, Gawrychowski et al. [ICALP, 2018] gave an improved upper bound of $O( {kn\ \mathrm{l}{{\mathrm{g}}^2}\ n} )$. This paper further reduces the upper bound to O(kn lg n). In addition, this paper presents a simple $O( {{{k}^2}n} )$-time algorithm. It is the fastest when k = O(lg n). Especially, when k = O(1), linear time is achieved.

Abstract. Motivated by an application in cancer genomics, Hajirasouliha and Raphael [ Proceedings of the 14 th International Workshop on Algorithms in Bioinformatics, 2014, pp. 354–367] proposed the split-row problem (SR). In this problem, an [Formula: see text] binary matrix [Formula: see text] is given. A split-row operation on [Formula: see text] is defined as replacing a row [Formula: see text] by [Formula: see text] rows [Formula: see text] whose bitwise OR is equal to [Formula: see text]. The cost of the operation is the number of additional rows induced, that is, [Formula: see text]. The goal is to find a sequence of split-row operations that transforms [Formula: see text] into a matrix corresponding to a perfect phylogeny and the total cost is minimized. Recently, Hujdurović et al. [ ACM Trans. Algorithms, 14 (2018), 26] proved the APX-hardness of SR and presented efficient exact and approximation algorithms. The parameterized study of SR was left as a direction for future work. Let [Formula: see text] denote the minimum total cost. This paper gives an [Formula: see text]-time exact algorithm for SR. This result indicates that SR is fixed-parameter tractable when parameterized by [Formula: see text]. In addition, in the worst case, our algorithm requires [Formula: see text] time, significantly improving the previous upper bound of [Formula: see text]. Hujdurović et al.’s exact algorithm can be modified to solve a variant of SR, called the distinct split-row problem (DSR). Our algorithm can be adapted to this variant as well. In addition, our algorithms can be extended to solve SR and DSR with the following additional constraint: only the rows in a given subset are allowed to be split.

The maximum agreement subtree method determines the consensus of a collection of phylogenetic trees by identifying maximum cardinality subsets of leaves for which all input trees agree. The trees induced by these maximum cardinality subsets are maximum agreement subtrees (MASTs). A single MAST may be misleading, since there can exist two MASTs which share almost no leaves; nevertheless, it may be impossible to inspect all MASTs, since the number of MASTs can be exponential in the number of leaves. To overcome this drawback, Swenson et al. suggested to further summarize the information common to all MASTs by their intersection, which is called the kernel agreement subtree (KAST). The construction of the KAST is the focus of this paper. Swenson et al. had an O(kn3+ n4+ nd + 1)O(kn3+n4+nd+1) time algorithm for computing the KAST of kk trees on nn leaves, in which at least one tree has maximum degree dd. In this paper, an O(kn3+ nd)O(kn3+nd)-time algorithm is presented. We demonstrate the efficiency of our algorithm on simulated trees as well as on ribosomal RNA alignments, where trees with 13,000 taxa took only hours to process, whereas the previous algorithm did not terminate after a week of computation.

Tree comparison metrics are an important tool for the study of phylogenetic trees. Path-difference distances measure the dissimilarity between two phylogenetic trees (on the same set of taxa) by comparing their path-length vectors. Various norms can be applied to this distance. Three important examples are the $l_{1}\text{-},\;l_{2}\text{-}$l1-,l2-, and $l_{{\infty }}$l∞-norms. The previous best algorithms for computing path-difference distances all have $O(n^{2})$O(n2) running time. In this paper, we show how to compute the $l_{1}$l1-norm path-difference distance in $O(n\;{\log}^{2}\;n)$O(nlog2n) time and how to compute the $l_{2}$l2- and $l_{{\infty }}$l∞-norm path-difference distances in $O(n\;{\log}\;n)$O(nlogn) time. By extending the presented algorithms, we also show that the $l_{p}$lp-norm path-difference distance can be computed in $O(pn\;{\log}^{2}\;n)$O(pnlog2n) time for any positive integer $p$p. In addition, when the integer $p$p is even, we show that the distance can be computed in $O(p^{2}n\;{\log}\;n)$O(p2nlogn) time as well.

The focus of this paper is the frequent gene team problem. Given a quorum parameter μ and a set of m genomes, the problem is to find gene teams that occur in at least μ of the given genomes. In this paper, a new algorithm is presented. Previous solutions are efficient only when μ is small. Unlike previous solutions, the presented algorithm does not rely on examining every combination of μ genomes. Its time complexity is independent of μ. Under some realistic assumptions, the practical running time is estimated to be , where n is the maximum length of the input genomes. Experiments showed that the presented algorithm is extremely efficient. For any μ, it takes less than 1 second to process 100 bacterial genomes and takes only 10 minutes to process 2,000 genomes. The presented algorithm can be used as an effective tool for large scale genome analyses.

The problem of finding all reversals that take a permutation one step closer to a target permutation is called the all sorting reversals problem (the ASR problem). For this problem, Siepel had an O(n (3))-time algorithm. Most complications of his algorithm stem from some peculiar structures called bad components. Since bad components are very rare in both real and simulated data, it is practical to study the ASR problem with no bad components. For the ASR problem with no bad components, Swenson et al. gave an O (n(2))-time algorithm. Very recently, Swenson found that their algorithm does not always work. In this paper, a new algorithm is presented for the ASR problem with no bad components. The time complexity is O(n(2)) in the worst case and is linear in the size of input and output in practice.

An important model of a conserved gene cluster is called the gene team model, in which a chromosome is defined to be a permutation of distinct genes and a gene team is defined to be a set of genes that appear in two or more species, with the distance between adjacent genes in the team for each chromosome always no more than a certain threshold δ. A gene team tree is a succinct way to represent all gene teams for every possible value of δ. The previous fastest algorithm for constructing a gene team tree of two chromosomes requires O(n lg n lglg n) time, which was given by Wang and Lin. Its bottleneck is a problem called the maximum-gap problem. In this paper, by presenting an improved algorithm for the maximum-gap problem, we reduce the upper bound of the gene team tree problem to O(n lg n α(n)). Since α grows extremely slowly, this result is almost as efficient as the current best upper bound, O(n lg n), for finding the gene teams of a fixed δ value. Our new algorithm is very efficient from both the theoretical and practical points of view. Wang and Lin's gene-team-tree algorithm can be extended to k chromosomes with complexity O(kn lg n lglg n). Similarly, our improved algorithm for the maximum-gap problem reduces this running time to O(kn lg n α(n)). In addition, it also provides new upper bounds for the gene team tree problem on general sequences, in which multiple copies of the same gene are allowed.

The focus of this paper is the problem of finding all nested common intervals of two general sequences. Depending on the treatment one wants to apply to duplicate genes, Blin et al. introduced three models to define nested common intervals of two sequences: the uniqueness, the free-inclusion, and the bijection models. We consider all the three models. For the uniqueness and the bijection models, we give O(n + N(out))-time algorithms, where N(out) denotes the size of the output. For the free-inclusion model, we give an O(n(1+ε) + N(out))-time algorithm, where ε > 0 is an arbitrarily small constant. We also present an upper bound on the size of the output for each model. For the uniqueness and the free-inclusion models, we show that N(out) = O(n2). Let C = Σ(g∈Γ) o1(g)o2(g), where Γ is the set of distinct genes, and o1(g) and o2(g) are, respectively, the numbers of copies of gene g in the two given sequences. For the bijection model, we show that N(out) = O(Cn). In this paper, we also study the problem of finding all approximate nested common intervals of two sequences on the bijection model. An O(δn + N(out))-time algorithm is presented, where δ denotes the maximum number of allowed gaps. In addition, we show that for this problem N(out) is O(δn3).

Identifying conserved gene clusters is an important step toward understanding the evolution of genomes and predicting the functions of genes. A famous model to capture the essential biological features of a conserved gene cluster is called the gene-team model. The problem of finding the gene teams of two general sequences is the focus of this paper. For this problem, He and Goldwasser had an efficient algorithm that requires O(mn) time using O(m + n) working space, where m and n are, respectively, the numbers of genes in the two given sequences. In this paper, a new efficient algorithm is presented. Assume m ≤ n. Let C = Σ(α)(∈)(Σ) o(1)(α)o(2)(α), where Σ is the set of distinct genes, and o(1)(α) and o(2)(α) are, respectively, the numbers of copies of α in the two given sequences. Our new algorithm requires O(min{C lg n, mn}) time using O(m + n) working space. As compared with He and Goldwasser's algorithm, our new algorithm is more practical, as C is likely to be much smaller than mn in practice. In addition, our new algorithm is output sensitive. Its running time is O(lg n) times the size of the output. Moreover, our new algorithm can be efficiently extended to find the gene teams of k general sequences in O(k C lg (n(1)n(2). . .n(k)) time, where n(i) is the number of genes in the ith input sequence.

A gene team is a set of genes that appear in two or more species, possibly in a different order yet with the distance between adjacent genes in the team for each chromosome always no more than a certain threshold δ. A gene team tree is a succinct way to represent all gene teams for every possible value of δ. In this paper, improved algorithms are presented for the problem of finding the gene teams of two chromosomes and the problem of constructing a gene team tree of two chromosomes. For the problem of finding gene teams, Beal et al. had an O(n lg2 n)-time algorithm. Our improved algorithm requires O(n lg t) time, where t ≤ n is the number of gene teams. For the problem of constructing a gene team tree, Zhang and Leong had an O(n lg2 n)-time algorithm. Our improved algorithm requires O(n lg n lglg n) time. Similar to Beal et al.'s gene team algorithm and Zhang and Leong's gene team tree algorithm, our improved algorithms can be extended to k chromosomes with the time complexities increased only by a factor of k.

In this article, efficient algorithms are presented for the minmax-regret 1-center and 1-median problems on a general graph and a tree with uncertain vertex weights. For the minmax-regret 1-center problem on a general graph, we improve the previous upper bound from O ( mn 2 log n ) to O ( mn log n ). For the problem on a tree, we improve the upper bound from O ( n 2 ) to O ( n log 2 n ). For the minmax-regret 1-median problem on a general graph, we improve the upper bound from O ( mn 2 log n ) to O ( mn 2 + n 3 log n ). For the problem on a tree, we improve the upper bound from O ( n log 2 n ) to O ( n log n ).

Let A be a sequence of n real numbers, L(1) and L(2) be two integers such that L(1) < or = L(2) , and R(1) and R(2) be two real numbers such that R(1) < or = R(2). An interval of A is feasible if its length is between L(1) and L(2) and its average is between R(1) and R(2). In this paper, we study the following problems: finding all feasible intervals of A, counting all feasible intervals of A, finding a maximum cardinality set of non-overlapping feasible intervals of A, locating a longest feasible interval of A, and locating a shortest feasible interval of A. The problems are motivated from the problem of locating CpG islands in biomolecular sequences. In this paper, we firstly show that all the problems have Omega (n log n)-time lower bound in the comparison model. Then, we use geometric approaches to design optimal algorithms for the problems. All the presented algorithms run in an on-line manner and use O(n) space.

Let T=(V, E) be an edge-weighted tree with |V|=n vertices embedded in the Euclidean plane. Let IE denote the set of all points on the edges of T. Let X and Y be two subsets of IE and let r be a positive real number. A subset D/spl sube/X is an X/Y/r-dominating set if every point in Y is within distance r of a point in D. The X/Y/r-dominating set problem is to find an X/Y/r-dominating set D* with minimum cardinality. Let p/spl ges/1 be an integer. The X/Y/p-center problem is to find a subset C*/spl sube/X of p points such that the maximum distance of any point in Y from C* is minimized. Let X and Y be either V or IE. In this paper, efficient parallel algorithms on the EREW PRAM are first presented for the X/Y/r-dominating set problem. The presented algorithms require O(log/sup 2/n) time for all cases of X and Y. Parallel algorithms on the EREW PRAM are then developed for the X/Y/p-center problem. The presented algorithms require O(log/sup 3/n) time for all cases of X and Y. Previously, sequential algorithms for these two problems had been extensively studied in the literature. However, parallel solutions with polylogarithmic time existed only for their special cases. The algorithms presented in this paper are obtained by using an interesting approach which we call the dependency-tree approach. Our results are examples of parallelizing sequential dynamic-programming algorithms by using the approach.

A Cartesian product network is obtained by applying the cross operation on two graphs. We study the problem of constructing the maximum number of edge-disjoint spanning trees (abbreviated to EDSTs) in Cartesian product networks. Let G=(V/sub G/, E/sub G/) be a graph having n/sub 1/ EDSTs and F=(V/sub F/, E/sub F/) be a graph having n/sub 2/ EDSTs. Two methods are proposed for constructing EDSTs in the Cartesian product of G and F, denoted by G/spl times/F. The graph G has t/sub 1/=|E/sub G/|/spl middot/n/sub 1/(|V/sub G/|-1) more edges than that are necessary for constructing n/sub 1/ EDSTs in it, and the graph F has t2=|E/sub F/'-n/sub 2/(|V/sub F/|-1) more edges than that are necessary for constructing n/sub 2/ EDSTs in it. By assuming that t/sub 1//spl ges/n/sub 1/ and t/sub 2//spl ges/n/sub 2/, our first construction shows that n/sub 1/+n/sub 2/ EDSTS can be constructed in G/spl times/F. Our second construction does not need any assumption and it constructs n/sub 1/+n/sub 2/-1 EDSTs in G/spl times/F. By applying the proposed methods, it is easy to construct the maximum numbers of EDSTs in many important Cartesian product networks, such as hypercubes, tori, generalized hypercubes, mesh connected trees, and hyper Petersen networks.

Let T=(V, E) be a tree with vertex set V and edge set E. Let n=|V|. Each e/spl isin/E has a non-negative length. In this paper, we first present an algorithm on the CREW PRAM for solving the V/V/r-dominating set problem on T, where r/spl ges/0 is a real number. The algorithm requires O(log/sup 2/ n) time using O(n log n) work. Applying this algorithm as a procedure for testing feasibility, the V/V/p-center problem on the CREW PRAM is solved in O(log/sup 2/ n) time using O(n log/sup 2/ n) work, where p/spl ges/1 is an integer. Previously, He and Yesha had proposed algorithms on the CREW PRAM for special cases of the V/V/r-dominating set and the V/V/p-center problems, in which r is an integer and the lengths of all edges are 1. Their V/V/r-dominating set algorithm requires O(log n log log n) time using O(n log n log log n) work; and their V/V/p-center algorithm requires O(log/sup 2/ n log log n) time using O(n log/sup 2/ n log log n) work. As compared with He and Yesha's results, ours are more general and more efficient from the aspect of work.

Location theory on networks has been widely investigated by researchers from different fields for more than thirty years due to its significance and practical value. Among various location problems, the p-center and the p-median problems are the most common. The p-facility k-centrum problem, introduced by Slater (1978), is a generalization of the above two problems. The objective is to minimize the sum of the k largest service distances from clients to their nearest servers. When p is an arbitrary integer, the problem is NP-hard on general networks. Therefore, most researchers have devoted to the single-facility case, i.e. p=1, or the case that the networks under consideration are trees. This paper focuses on the single-facility k-centrum problem on a tree. For this problem, Tamir (1996) had an O(nlog/sup 2/ n) time algorithm. In this paper, an O(nlog n) time algorithm with is proposed.

Let T be an edge-weighted tree. A p-core of T is a set of p mutually disjoint paths in T that minimizes the sum of the distances of all vertices in T from any of the p paths, where $p \geq 1$ is an integer. In this paper, an O(n) time algorithm is proposed for the case p = 2, where n is the number of vertices in T. Our algorithm improves the two O(n 2 ) time algorithms previously proposed by Becker and Perl [Discrete Appl. Math., 11 (1985), pp. 103--113]. With some modifications, the proposed algorithm can be implemented on the EREW PRAM in O(log 2 n ) time using O(n log n) work.

An edge is a bisector of a simple path if it contains the middle point of the path. Let T=(V,E) be a tree. Given a source vertex s /spl isin/ V, the single-source tree bisector problem is to find, for every vertex /spl upsi/ /spl isin/ V, a bisector of the simple path from s to /spl upsi/. The all-pairs tree bisector problem is to find for, every pair of vertices u, /spl upsi/ /spl isin/ V, a bisector of the simple path from u to /spl upsi/. In this paper, it is first shown that solving the single-source tree bisector problem of a weighted tree has a time lower bound /spl Omega/(n log n) in the sequential case. Then, efficient parallel algorithms are proposed on the EREW PRAM for the single-source and all-pairs tree bisector problems. Two O(log n) time single-source algorithms are proposed. One uses O(n) work and is for unweighted trees. The other uses O(n log n) work and is for weighted trees. Previous algorithms for the single-source problem could achieve the same time O(log n) and the same optimal work, O(n) for unweighted trees and O(n log n) for weighted trees, on the CRCW PRAM. The contribution of our single-source algorithms is the improvement from CRCW to EREW. One all-pairs parallel algorithm is proposed. It requires O(log n) time using O(n/sup 2/) work. All the proposed algorithms are cost-optimal. Efficient tree bisector algorithms have practical applications to several location problems on trees. Using the proposed algorithms, efficient parallel solutions for those problems are also presented.

Let G be an undirected graph and T be a spanning tree of G. In this paper, an efficient parallel algorithm is proposed for determining whether T is an unordered depth-first search tree of G. The proposed algorithm runs in O(m/p+log m) time using p processors on the EREW PRAM, where m is the number of edges contained in G. It is cost-optimal and achieves linear speedup.

An edge is a bisector of a simple path if it contains the middle point of the path. In this paper, efficient parallel algorithms are proposed on the EREW PRAM for the single-source and all-pairs tree bisector problems. Two O(log n) time single-source algorithms are proposed. One uses O(n) work and the other uses O(nlog n) work. The one using O(n) work is more efficient but only applicable to unweighted trees. One all-pairs parallel algorithm is proposed. It requires O(log n) time using O(n/sup 2/) work.

The first main contribution of this work is to propose an efficient VLSI architecture obtained by augmenting the Mesh with Multiple Broadcasting (MMB) with precharged 1-bit row and column buses. The new architecture, which we call Mesh with Hybrid Buses (MHB for short), is realizable in VLSI with no increase in the area or the wiring complexity of the MMB chip. Our second main contribution is to show that the MHB is extremely well-suited for solving an entire slew of digital geometry tasks. The MHB is not a reconfigurable architecture. Yet, quite remarkably, for a large number of fundamental digital geometry tasks, the MHB offers a level of performance previously attained only by reconfigurable architectures. Specifically, with a digital image pretiled onto a MHB of size /spl radic/n/spl times//spl radic/n one pixel per processor, we show that the problems of computing the convex hull of the image, computing the diameter and the width of the image, deciding whether a set of digital points is a digital line, computing the maximum distance between two images, deciding whether two images are linearly separable, computing several moments and low-level descriptors of the image, including the perimeter, area, center, and median row of its convex hull, can be solved in O(log n) time. By contrast, the fastest possible algorithms for the problems above on the MMB run in /spl Theta/(n/sup 1/6/) time. Finally, we go on to show that, with minor changes, our algorithms can be implemented to run within cost-optimality on a MHB of size /spl radic/n/log n/spl times//spl radic/n/log n.

A k-tree core of a tree network is a subtree with exactly k leaves that minimizes the total distance from vertices to the subtree. A k-tree center of a tree network is a subtree with exactly k leaves that minimizes the distance from the farthest vertex to the subtree. In this paper, two efficient parallel algorithms are proposed for finding a k-tree core and a k-tree center of a tree network, respectively. Both the proposed algorithms perform on the EREW PRAM in O(log n log n) time using O(n) work (time-processor product). Besides being efficient on the EREW PRAM, in the sequential case, our algorithm for finding a k-tree core of a tree network improves the two algorithms previously proposed.

In this paper, an efficient parallel algorithm is proposed for finding a k-tree core of a tree network. The proposed algorithm performs on the EREW PRAM in O(log n log* n) time using O(n) work.

Efficient emulations provide general methods to convert algorithms designed on a network into algorithms on smaller networks (with the same interconnection structure). In this paper, an optimal emulation for trees is proposed. With slight modification, our emulation can be applied to X-trees without loss of any efficiency. By the strategy of our emulation, optimal emulations for m-ary trees and pyramids can be obtained. An extended problem of the emulation problem on trees is to emulate a weighted tree, in which every node is associated with a weight by a smaller tree. In this paper, we also consider the extended problem and show that the problem is NP-hard.

In this paper, fast algorithms for simulating the CRCW shared-memory computer on reconfigurable meshes are proposed.

The algebraic path problem is a general description of a class of problems, including some important graph problems such as transitive closure, all pairs shortest paths, minimum spanning tree, etc. In this work, the algebraic path problem is solved on a processor array with a reconfigurable bus system. The proposed algorithms are based on repeated matrix multiplications. The multiplication of two n*n matrices takes O(log n) time in the worst case, but, for some special cases, O(1) time is possible. It is shown that three instances of the algebraic path problem, transitive closure, all pairs shortest paths, and minimum spanning tree, can be solved in O(log n) time, which is as fast as on the CRCW PRAM.>

The transitive closure problem in O(1) time is solved by a new method that is far different from the conventional solution method. On processor arrays with reconfigurable bus systems, two O(1) time algorithms are proposed for computing the transitive closure of an undirected graph. One is designed on a three-dimensional n*n*n processor array with a reconfigurable bus system, and the other is designed on a two-dimensional n/sup 2/*n/sup 2/ processor array with a reconfigurable bus system, where n is the number of vertices in the graph. Using the O(1) time transitive closure algorithms, many other graph problems are solved in O(1) time. These problems include recognizing bipartite graphs and finding connected components, articulation points, biconnected components, bridges, and minimum spanning trees in undirected graphs.>