In the p-Cluster Vertex Deletion problem, we are given a graph and two parameters k and p, and the goal is to determine if there exists a subset X of at most k vertices such that the removal of X results in a graph co...
详细信息
In the p-Cluster Vertex Deletion problem, we are given a graph and two parameters k and p, and the goal is to determine if there exists a subset X of at most k vertices such that the removal of X results in a graph consisting of exactly p disjoint maximal cliques. Let . In this paper, we design a branching algorithm with time complexity , where depends on r and has a rough upper bound . With a more precise analysis, we show that for;for;and for , respectively. Our algorithm also works with the same time complexity for the variant that the number of clusters is at most p. Our result improves the previous best time complexity and implies that for fixed p the problem can be solved as efficiently as Vertex Cover.
In this paper, we develop a new parameterized algorithm for the INDEPENDENT FEEDBACK VERTEX SET problem. Given a graph G=(V, E), the goal of the problem is to determine whether there exists a vertex subset F C V such ...
详细信息
In this paper, we develop a new parameterized algorithm for the INDEPENDENT FEEDBACK VERTEX SET problem. Given a graph G=(V, E), the goal of the problem is to determine whether there exists a vertex subset F C V such that V F induces a forest in G and F is an independent set. We show that there exists a parameterized algorithm that can determine whether a graph contains an IFVS of size k or not in time O(4(k)n(2)). To our best knowledge, this result improves the known upper bound for this problem, which is O(5(k)n(o(1))). (C) 2014 Elsevier B.V. All rights reserved.
We consider the problem of covering a given set of points in the Euclidean space R-m by a small number k of hyperplanes of dimensions bounded by d, where d <= m. We present a very simple parameterized algorithm for...
详细信息
We consider the problem of covering a given set of points in the Euclidean space R-m by a small number k of hyperplanes of dimensions bounded by d, where d <= m. We present a very simple parameterized algorithm for the problem, and give thorough mathematical analysis to prove the correctness and derive the complexity of the algorithm. When the algorithm is applied on the standard HYPERPLANE-COVER problem in R-d, it runs in time O*(k((d-1)k)/1.3(k)) improving the previous best algorithm of running time O*(k(dk+d)) for the problem. When the algorithm is applied on the LINE-COVER problem in R-2, it runs in time O*(k(k)/1.35(k)) improving the previous best algorithm of running time O*(k(2)k/4.84(k)) for the problem. (C) 2010 Elsevier B.V. All rights reserved.
The parameterized NODE MULTIWAY CUT problem is for a given graph to find a separator of size bounded by k whose removal separates a collection of terminal sets in the graph. In this paper, we develop an O(k4(k)n(3)) t...
详细信息
The parameterized NODE MULTIWAY CUT problem is for a given graph to find a separator of size bounded by k whose removal separates a collection of terminal sets in the graph. In this paper, we develop an O(k4(k)n(3)) time algorithm for this problem, significantly improving the previous algorithm of time O(4k(3)n(5)) for the problem. Our result gives the first polynomial time algorithm for the MINIMUM NODE MULTIWAY CUT problem when the separator size is bounded by O(log n).
An important problem in structural bioinformatics is to determine the secondary structure of an RNA molecule from its primary sequence. The problem is nondeterministic polynomial time hard when the secondary structure...
详细信息
An important problem in structural bioinformatics is to determine the secondary structure of an RNA molecule from its primary sequence. The problem is nondeterministic polynomial time hard when the secondary structure of the sequence may contain pseudoknot structures. In this paper, we develop a parameterized algorithm that can efficiently predict the secondary structure of an RNA sequence that may contain pseudoknot structures with high accuracy. We use a graph model to describe the overlapping relationships of energetically stable stems in the sequence. A new structure parameter is identified for the graph. Based on this parameter, we develop a parameterized algorithm that can efficiently compute the most energetically favored secondary structure from the primary sequence of an RNA molecule. Our experiments show that the parameter is a small integer for many RNA molecules and our testing results also demonstrate the advantages of this new algorithm in prediction accuracy and computational efficiency over existing prediction tools.
The Individual Haplotyping MFR problem is a computational problem that, given a set of DNA sequence fragment data of an individual, induces the corresponding haplotypes by dropping the minimum number of fragments. Baf...
详细信息
The Individual Haplotyping MFR problem is a computational problem that, given a set of DNA sequence fragment data of an individual, induces the corresponding haplotypes by dropping the minimum number of fragments. Bafna, Istrail, Lancia, and Rizzi proposed an algorithm of time O(2(2k)m(2)n + 2(3k)m(3)) for the problem, where m is the number of fragments, n is the number of SNP sites, and k is the maximum number of holes in a fragment. When there are mate-pairs in the input data, the parameter k can be as large as 100, which would make the Bafna-Istrail-Lancia-Rizzi algorithm impracticable. The current paper introduces a new algorithm PM-MFR of running time O(nk(2)3(k2) + m logm + mk(1)), where k(1) is the maximum number of SNP sites that a fragment covers (k(1) is smaller than n), and k(2) is the maximum number of fragments that cover a SNP site (k(2) is usually about 10). Since the time complexity of the algorithm PM-MFR is not directly related to the parameter k, the algorithm solves the Individual Haplotyping MFR problem with mate-pairs more efficiently and is more practical in real biological applications.
In this paper, we study the Transcription Factor Binding Sites (TFBS) prediction problem in bioinformatics. We develop a novel parameterized approach that can efficiently explore the space of all possible locations of...
详细信息
ISBN:
(纸本)9783319093307;9783319093291
In this paper, we study the Transcription Factor Binding Sites (TFBS) prediction problem in bioinformatics. We develop a novel parameterized approach that can efficiently explore the space of all possible locations of TFBSs in a set of homologous sequences with high accuracy. The exploration is performed by an ensemble of a few Hidden Markov Models (HMM), where the size of the ensemble is the parameter of the algorithm. The ensemble is initially constructed through the local alignments between two sequences that have the lowest similarity value in the sequence set, the parameters of each HMM in the ensemble are revised when the remaining sequences in the set are scanned through by it one by one. A list of possible TFBSs are generated when all sequences in the set have been processed by the ensemble. Testing results showed that this approach can accurately handle the cases where a single sequence may contain multiple binding sites and thus has advantages over most of the existing approaches when a sequence may contain multiple binding sites.
The parameterized NODE MULTIWAY CUT problem is for a given graph to find a separator of size bounded by k whose removal separates a collection of terminal sets in the graph. In this paper, we develop an O(k4(k)n(3)) t...
详细信息
ISBN:
(纸本)3540739483
The parameterized NODE MULTIWAY CUT problem is for a given graph to find a separator of size bounded by k whose removal separates a collection of terminal sets in the graph. In this paper, we develop an O(k4(k)n(3)) time algorithm for this problem, significantly improving the previous algorithm of time O(4k(3)n(5)) for the problem. Our result gives the first polynomial time algorithm for the MINIMUM NODE MULTIWAY CUT problem when the separator size is bounded by O(log n).
The Cluster Editing problem asks to transform a graph by at most k edge modifications into a disjoint union of cliques. The problem is NP-complete, but several parameterized algorithms are known. We present a novel se...
详细信息
The Cluster Editing problem asks to transform a graph by at most k edge modifications into a disjoint union of cliques. The problem is NP-complete, but several parameterized algorithms are known. We present a novel search tree algorithm for the problem, which improves running time from 0(1.76(k) + m + n) to 0(1.62(k) + m + n) for m edges and n vertices. In detail, we can show that we can always branch with branching vector (2, 1) or better, resulting in the golden ratio as the base of the search tree size. Our algorithm uses a well-known transformation to the integer-weighted counterpart of the problem. To achieve our result, we combine three techniques: First, we show that zero-edges in the graph enforce structural features that allow us to branch more efficiently. This is achieved by keeping track of the parity of merged vertices. Second, by repeatedly branching we can isolate vertices, releasing cost. Third, we use a known characterization of graphs with few conflicts. We then show that Integer-Weighted Cluster Editing remains NP-hard for graphs that have a particularly simple structure: namely, a clique minus the edges of a triangle. (C) 2012 Elsevier B.V. All rights reserved.
Based on the characters of DNA fragments, the paper introduces a parameterized algorithm for the minimum error correction with genotype information (MEC/GI) model of the haplotype assembly problem. Its time complexity...
详细信息
Based on the characters of DNA fragments, the paper introduces a parameterized algorithm for the minimum error correction with genotype information (MEC/GI) model of the haplotype assembly problem. Its time complexity is O(nk22k2 + mlogm + mk1), where m is the number of fragments, n is the number of SNP sites, k1 is the maximum number of SNP sites that a fragment covers (usually less than 10), and k2 is the maximum number of the fragments covering a SNP site (usually not greater than 10). For the practical fragment data, the algorithm can solve the MEC/GI problem efficiently even if m and n are rather great, and it is scalable and applicable in practice.
暂无评论