检索结果-内蒙古大学图书馆

The Feedback Arc Set Problem with Triangle Inequality Is a Vertex Cover Problem

ALGORITHMICA 2014年第2期70卷 326-339页

作者： Mastrolilli, Monaldo IDSIA USI SUPSI Lugano Switzerland

We consider the (precedence constrained) Minimum Feedback Arc Set problem with triangle inequalities on the weights, which finds important applications in problems of ranking with inconsistent information. We present a surprising structural insight showing that the problem is a special case of the minimum vertex cover in hypergraphs with edges of size at most 3.

关键词： Feedback arc set problem Approximation algorithms integer linear program formulation

来源：评论

学校读者我要写书评

暂无评论

ILP-based maximum likelihood genome scaffolding

引用

BMC BIOINFORMATICS 2014年第9期15卷 1-12页

作者： Lindsay, James Salooti, Hamed Mandoiu, Ion Zelikovsky, Alex Univ Connecticut Dept Comp Sci & Engn Storrs CT 06269 USA Georgia State Univ Dept Comp Sci Atlanta GA 30303 USA

Background: Interest in de novo genome assembly has been renewed in the past decade due to rapid advances in high-throughput sequencing (HTS) technologies which generate relatively short reads resulting in highly fragmented assemblies consisting of contigs. Additional long-range linkage information is typically used to orient, order, and link contigs into larger structures referred to as scaffolds. Due to library preparation artifacts and erroneous mapping of reads originating from repeats, scaffolding remains a challenging problem. In this paper, we provide a scalable scaffolding algorithm (SILP2) employing a maximum likelihood model capturing read mapping uncertainty and/or non-uniformity of contig coverage which is solved using integer linear programming. A Non-Serial Dynamic programming (NSDP) paradigm is applied to render our algorithm useful in the processing of larger mammalian genomes. To compare scaffolding tools, we employ novel quantitative metrics in addition to the extant metrics in the field. We have also expanded the set of experiments to include scaffolding of low-complexity metagenomic samples. Results: SILP2 achieves better scalability throughg a more efficient NSDP algorithm than previous release of SILP. The results show that SILP2 compares favorably to previous methods OPERA and MIP in both scalability and accuracy for scaffolding single genomes of up to human size, and significantly outperforms them on scaffolding low-complexity metagenomic samples. Conclusions: Equipped with NSDP, SILP2 is able to scaffold large mammalian genomes, resulting in the longest and most accurate scaffolds. The ILP formulation for the maximum likelihood model is shown to be flexible enough to handle metagenomic samples.

关键词： integer linear program Read Pair integer linear program formulation Metagenomic Sample Maximum Likelihood Model

来源：评论

学校读者我要写书评

暂无评论

Optimized Trajectory of a Robot Deploying Wireless Sensor Nodes 7

Optimized Trajectory of a Robot Deploying Wireless Sensor No...

引用

IFIP Wireless Days (WD)

作者： Khoufi, Ines Livolant, Erwan Minet, Pascale Hadded, Mohamed Laouiti, Anis Inria F-78153 Le Chesnay France CNRS Samovar UMR 5157 TELECOM SudParis F-91011 Evry France

ISBN: (纸本)9781479966066

Mobile robots can be used to deploy static wireless sensor nodes to achieve the coverage and connectivity requirements of the applications considered. Many solutions have been provided in the literature to compute the set of locations where the sensor nodes should be placed. In this paper, we show how this set of locations can be used by a mobile robot to optimize its tour to deploy the sensor nodes to their right locations. In order to reduce both the energy consumed by the robot, its exposure time to a hostile environment, as well as the time at which the wireless network becomes operational, the optimal tour of the robot is this minimizing the delay. This delay must take into account not only the time needed by the robot to travel the tour distance but also the time spent in the rotations performed by the robot each time it changes its direction. This problem is called the Robot Deploying Sensor nodes problem, in short RDS. We first show how this problem differs from the well-known traveling salesman problem. We then propose an integer linear program formulation of the RDS problem. We propose various algorithms relevant to iterative improvement by exchanging tour edges, genetic approach and hybridization. The solutions provided by these algorithms are compared and their closeness to the optimal is evaluated in various configurations.

关键词： integer programming linear programming mobile robots sensor placement travelling salesman problems wireless sensor networks RDS energy consumption integer linear program formulation mobile robot optimized trajectory robot deploying sensor nodes problem static wireless sensor nodes traveling salesman problem wireless network Approximation algorithms Genetics Robot sensing systems Sociology Wireless communication Wireless sensor networks travelling salesman problems Mobile robots Wireless sensor networks Wireless networks Manipulator sensing systems radio data systems Respiratory Distress Syndrome TST gene Robot sensor placement Sociology CARRIER SYSTEM Approximation algorithms linear programming integer programming

来源：评论

学校读者我要写书评

暂无评论

On the lot-type design problem

引用

OPTIMIZATION METHODS & SOFTWARE 2010年第2期25卷 217-227页

作者： Gaul, Constantin Kurz, Sascha Rambau, Joerg Univ Bayreuth Dept Math Phys & Comp Sci D-95440 Bayreuth Germany

We consider the problem of approximating the branch- and size-dependent demand of a fashion discounter with many branches by a distributing process being based on the branch delivery restricted to integral multiples of lots from a small set of available lot-types. We propose a formalized model that arises from a practical cooperation with an industry partner. Besides an integer linear programming formulation, we provide an appropriate primal heuristic for this problem.

关键词： p-median problem facility location problem integer linear program formulation primal heuristic real-world data location-allocation

来源：评论

学校读者我要写书评

暂无评论

Constructing majority-rule supertrees

引用

ALGORITHMS FOR MOLECULAR BIOLOGY 2010年第1期5卷 2-2页

作者： Dong, Jianrong Fernandez-Baca, David McMorris, F. R. Iowa State Univ Dept Comp Sci Ames IA 50011 USA IIT Dept Appl Math Chicago IL 60616 USA

Background: Supertree methods combine the phylogenetic information from multiple partially-overlapping trees into a larger phylogenetic tree called a supertree. Several supertree construction methods have been proposed to date, but most of these are not designed with any specific properties in mind. Recently, Cotton and Wilkinson proposed extensions of the majority-rule consensus tree method to the supertree setting that inherit many of the appealing properties of the former. Results: We study a variant of one of Cotton and Wilkinson's methods, called majority-rule (+) supertrees. After proving that a key underlying problem for constructing majority-rule (+) supertrees is NP-hard, we develop a polynomial-size exact integer linear programming formulation of the problem. We then present a data reduction heuristic that identifies smaller subproblems that can be solved independently. While this technique is not guaranteed to produce optimal solutions, it can achieve substantial problem-size reduction. Finally, we report on a computational study of our approach on various real data sets, including the 121-taxon, 7-tree Seabirds data set of Kennedy and Page. Conclusions: The results indicate that our exact method is computationally feasible for moderately large inputs. For larger inputs, our data reduction heuristic makes it feasible to tackle problems that are well beyond the range of the basic integer programming approach. Comparisons between the results obtained by our heuristic and exact solutions indicate that the heuristic produces good answers. Our results also suggest that the majority-rule (+) approach, in both its basic form and with data reduction, yields biologically meaningful phylogenies.

关键词： integer linear program Representative Selection Input Tree integer linear program formulation Supertree Method

来源：评论

学校读者我要写书评

暂无评论

On optimal comparability editing with applications to molecular diagnostics

引用

BMC BIOINFORMATICS 2009年第Sup1期10卷 S61-S61页

作者： Boecker, Sebastian Briesemeister, Sebastian Klau, Gunnar W. CWI NL-1090 GB Amsterdam Netherlands Univ Jena Inst Informat Jena Germany Jena Ctr Bioinformat Jena Germany Univ Tubingen ZBIT WSI Div Simulat Biol Syst D-72074 Tubingen Germany

Background: The COMPARABILITY EDITING problem appears in the context of hierarchical disease classification based on noisy data. We are given a directed graph G representing hierarchical relationships between patient subgroups. The task is to identify the minimum number of edge insertions or deletions to transform G into a transitive graph, that is, if edges (u, v) and (v, w) are present then edge (u, w) must be present, too. Results: We present two new approaches for the problem based on fixed-parameter algorithmics and integer linear programming. In contrast to previously used heuristics, our approaches compute provably optimal solutions. Conclusion: Our computational results demonstrate that our exact algorithms are by far more efficient in practice than a previously used heuristic approach. In addition to the superior running time performance, our algorithms are capable of enumerating all optimal solutions, and naturally solve the weighted version of the problem.

关键词： integer linear program Input Graph Reduction Rule integer linear program formulation Transitive Graph

来源：评论

学校读者我要写书评

暂无评论

Accurate multiple sequence-structure alignment of RNA sequences using combinatorial optimization

引用

BMC BIOINFORMATICS 2007年第1期8卷 271-271页

作者： Bauer, Markus Klau, Gunnar W. Reinert, Knut Free Univ Berlin Dept Math & Comp Sci D-14195 Berlin Germany Sch Computat Biol & Sci Comp Int Max Planck Res Berlin Germany DFG Res Ctr Matheon Berlin Germany

Background: The discovery of functional non- coding RNA sequences has led to an increasing interest in algorithms related to RNA analysis. Traditional sequence alignment algorithms, however, fail at computing reliable alignments of low- homology RNA sequences. The spatial conformation of RNA sequences largely determines their function, and therefore RNA alignment algorithms have to take structural information into account. Results: We present a graph- based representation for sequence- structure alignments, which we model as an integer linear program ( ILP). We sketch how we compute an optimal or near- optimal solution to the ILP using methods from combinatorial optimization, and present results on a recently published benchmark set for RNA alignments. Conclusion: The implementation of our algorithm yields better alignments in terms of two published scores than the other programs that we tested: This is especially the case with an increasing number of input sequences. Our program LARA is freely available for academic purposes from http:// www. planet- lisa. net.

关键词： Structural Alignment integer linear program formulation Reference Alignment Pairwise Sequence Identity Base Pair Probability

来源：评论

学校读者我要写书评

暂无评论

Direct maximum parsimony phylogeny reconstruction from genotype data

引用

BMC BIOINFORMATICS 2007年第1期8卷 472-472页

作者： Sridhar, Srinath Lam, Fumei Blelloch, Guy E. Ravi, R. Schwartz, Russell Carnegie Mellon Univ Dept Biol Sci Pittsburgh PA 15213 USA Carnegie Mellon Univ Dept Comp Sci Pittsburgh PA 15213 USA Brown Univ Dept Comp Sci Providence RI 02912 USA Carnegie Mellon Univ Tepper Sch Business Pittsburgh PA 15213 USA

Background: Maximum parsimony phylogenetic tree reconstruction from genetic variation data is a fundamental problem in computational genetics with many practical applications in population genetics, whole genome analysis, and the search for genetic predictors of disease. Efficient methods are available for reconstruction of maximum parsimony trees from haplotype data, but such data are difficult to determine directly for autosomal DNA. Data more commonly is available in the form of genotypes, which consist of conflated combinations of pairs of haplotypes from homologous chromosomes. Currently, there are no general algorithms for the direct reconstruction of maximum parsimony phylogenies from genotype data. Hence phylogenetic applications for autosomal data must therefore rely on other methods for first computationally inferring haplotypes from genotypes. Results: In this work, we develop the first practical method for computing maximum parsimony phylogenies directly from genotype data. We show that the standard practice of first inferring haplotypes from genotypes and then reconstructing a phylogeny on the haplotypes often substantially overestimates phylogeny size. As an immediate application, our method can be used to determine the minimum number of mutations required to explain a given set of observed genotypes. Conclusion: Phylogeny reconstruction directly from unphased data is computationally feasible for moderate-sized problem instances and can lead to substantially more accurate tree size inferences than the standard practice of treating phasing and phylogeny construction as two separate analysis stages. The difference between the approaches is particularly important for downstream applications that require a lower-bound on the number of mutations that the genetic region has undergone.

关键词： Maximum Parsimony integer linear program Steiner Tree integer linear program formulation Ancestral Recombination Graph

来源：评论

学校读者我要写书评

暂无评论

A combinatorial optimization approach for diverse motif finding applications

引用

ALGORITHMS FOR MOLECULAR BIOLOGY 2006年第0期1卷 13-13页

作者： Zaslavsky, Elena Singh, Mona Princeton Univ Dept Comp Sci Princeton NJ 08544 USA Princeton Univ Lewis Sigler Inst Integrat Genom Princeton NJ 08544 USA

Background: Discovering approximately repeated patterns, or motifs, in biological sequences is an important and widely-studied problem in computational molecular biology. Most frequently, motif finding applications arise when identifying shared regulatory signals within DNA sequences or shared functional and structural elements within protein sequences. Due to the diversity of contexts in which motif finding is applied, several variations of the problem are commonly studied. Results: We introduce a versatile combinatorial optimization framework for motif finding that couples graph pruning techniques with a novel integer linear programming formulation. Our approach is flexible and robust enough to model several variants of the motif finding problem, including those incorporating substitution matrices and phylogenetic distances. Additionally, we give an approach for determining statistical significance of uncovered motifs. In testing on numerous DNA and protein datasets, we demonstrate that our approach typically identifies statistically significant motifs corresponding to either known motifs or other motifs of high conservation. Moreover, in most cases, our approach finds provably optimal solutions to the underlying optimization problem. Conclusion: Our results demonstrate that a combined graph theoretic and mathematical programming approach can be the basis for effective and powerful techniques for diverse motif finding applications.

关键词： integer linear program Motif Finding Oxyr integer linear program formulation Phylogenetic Footprinting

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：