The individual haplotyping problem is a computing problem of reconstructing two haplotypes for an individual based on several optimal criteria from one's fragments sequencing data. This paper is based on the fact ...
详细信息
Determining whether a parameterized problem is kernelizable and has a small kernel size has recently become one of the most interesting topics of research in the area of parameterized complexity and algorithms. Theore...
详细信息
Determining whether a parameterized problem is kernelizable and has a small kernel size has recently become one of the most interesting topics of research in the area of parameterized complexity and algorithms. Theoretically, it has been proved that a parameterized problem is kernelizable if and only if it is fixed-parameter tractable. Practically, applying a data reduction algorithm to reduce an instance of a parameterized problem to an equivalent smaller instance (i.e., a kernel) has led to very efficient algorithms and now goes hand-in-hand with the design of practical algorithms for solving NP-hard problems. Well-known examples of such parameterized problems include the vertex cover problem, which is kernelizable to a kernel of size bounded by 2k, and the planar dominating set problem, which is kernelizable to a kernel of size bounded by 335k. In this paper we develop new techniques to derive upper and lower bounds on the kernel size for certain parameterized problems. In terms of our lower bound results, we show, for example, that unless P = NP, planar vertex cover does not have a problem kernel of size smaller than 4k/3, and planar independent set and planar dominating set do not have kernels of size smaller than 2k. In terms of our upper bound results, we further reduce the upper bound on the kernel size for the planar dominating set problem to 67k, improving significantly the 335k previous upper bound given by Alber, Fellows, and Niedermeier [J. ACM, 51 (2004), pp. 363-384]. This latter result is obtained by introducing a new set of reduction and coloring rules, which allows the derivation of nice combinatorial properties in the kernelized graph leading to a tighter bound on the size of the kernel. The paper also shows how this improved upper bound yields a simple and competitive algorithm for the planar dominating set problem.
Computational alignment of a biopolymer sequence (e. g., an RNA or a protein) to a structure is an effective approach to predict and search for the structure of new sequences. To identify the structure of remote homol...
详细信息
Computational alignment of a biopolymer sequence (e. g., an RNA or a protein) to a structure is an effective approach to predict and search for the structure of new sequences. To identify the structure of remote homologs, the structure-sequence alignment has to consider not only sequence similarity, but also spatially conserved conformations caused by residue interactions and, consequently, is computationally intractable. It is difficult to cope with the inefficiency without compromising alignment accuracy, especially for structure search in genomes or large databases. This paper introduces a novel method and a parameterized algorithm for structure-sequence alignment. Both the structure and the sequence are represented as graphs, where, in general, the graph for a biopolymer structure has a naturally small tree width. The algorithm constructs an optimal alignment by finding in the sequence graph the maximum valued subgraph isomorphic to the structure graph. It has the computational time complexity O(k(t)N(2)) for the structure of N residues and its tree decomposition of width t. Parameter k, small in nature, is determined by a statistical cutoff for the correspondence between the structure and the sequence. This paper demonstrates a successful application of the algorithm to RNA structure search used for noncoding RNA identification. An application to protein threading is also discussed.
Computational alignment of a biopolymer sequence (e. g., an RNA or a protein) to a structure is an effective approach to predict and search for the structure of new sequences. To identify the structure of remote homol...
详细信息
Computational alignment of a biopolymer sequence (e. g., an RNA or a protein) to a structure is an effective approach to predict and search for the structure of new sequences. To identify the structure of remote homologs, the structure-sequence alignment has to consider not only sequence similarity, but also spatially conserved conformations caused by residue interactions and, consequently, is computationally intractable. It is difficult to cope with the inefficiency without compromising alignment accuracy, especially for structure search in genomes or large databases. This paper introduces a novel method and a parameterized algorithm for structure-sequence alignment. Both the structure and the sequence are represented as graphs, where, in general, the graph for a biopolymer structure has a naturally small tree width. The algorithm constructs an optimal alignment by finding in the sequence graph the maximum valued subgraph isomorphic to the structure graph. It has the computational time complexity O(k(t)N(2)) for the structure of N residues and its tree decomposition of width t. Parameter k, small in nature, is determined by a statistical cutoff for the correspondence between the structure and the sequence. This paper demonstrates a successful application of the algorithm to RNA structure search used for noncoding RNA identification. An application to protein threading is also discussed.
A sequence of exact algorithms to solve the VERTEX COVER and MAXIMUM INDEPENDENT SET problems have been proposed in the literature. All these algorithms appeal to a very conservative analysis that considers the size o...
详细信息
A sequence of exact algorithms to solve the VERTEX COVER and MAXIMUM INDEPENDENT SET problems have been proposed in the literature. All these algorithms appeal to a very conservative analysis that considers the size of the search tree, under a worst-case scenario, to derive an upper bound on the running time of the algorithm. In this paper we propose a different approach to analyze the size of the search tree. We use amortized analysis to show how simple algorithms, if analyzed properly, may perform much better than the upper bounds on their running time derived by considering only a worst-case scenario. This approach allows us to present a simple algorithm of running time O(1.194(k)k(2) + n) for the parameterized VERTEX COVER problem on degree-3 graphs, and a simple algorithm of running time O(1.1255 '') for the MAXIMUM INDEPENDENT SET problem on degree-3 graphs. Both algorithms improve the previous best algorithms for the problems.
The "jump number scheduling problem" has been shown to be NP-complete. However, for a fixed parameter k, El-Zahar and Schmerl show that the decision problem "is the jump number less than or equal to k?&...
详细信息
The "jump number scheduling problem" has been shown to be NP-complete. However, for a fixed parameter k, El-Zahar and Schmerl show that the decision problem "is the jump number less than or equal to k?" is solvable in polynomial time. Their algorithm has a running time in excess of O(n(k!)), where n is the size of the schedule and k is a fixed parameter bounding the number of jumps permitted. We obtain a significant improvement on this by giving a linear-time constructive algorithm that outputs a schedule with less than or equal to k jumps, if one exists, or no otherwise. (C) 2001 Elsevier Science B.V. All rights reserved.
暂无评论