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

COMBINATORIAL algorithms FOR DNA-SEQUENCE ASSEMBLY

ALGORITHMICA 1995年第1-2期13卷 7-51页

作者： KECECIOGLU, JD MYERS, EW UNIV ARIZONA DEPT COMP SCI TUCSON AZ 85721 USA

The trend toward very large DNA sequencing projects, such as those being undertaken as part of the Human Genome Program, necessitates the development of efficient and precise algorithms for assembling a long DNA sequence from the fragments obtained by shotgun sequencing or other methods. The sequence reconstruction problem that we take as our formulation of DNA sequence assembly is a variation of the shortest common superstring problem, complicated by the presence of sequencing errors and reverse complements of fragments. Since the simpler superstring problem is NP-hard, any efficient reconstruction procedure must resort to heuristics. In this paper, however, a four-phase approach based on rigorous design criteria is presented, and has been found to be very accurate in practice. Our method is robust in the sense that it can accommodate high sequencing error rates, and list a series of alternate solutions in the event that several appear equally good. Moreover, it uses a limited form of multiple sequence alignment to detect, and often correct, errors in the data. Our combined algorithm has successfully reconstructed nonrepetitive sequences of length 50,000 sampled at error rates of as high as 10%.

关键词： COMPUTATIONAL BIOLOGY branch-and-bound algorithms APPROXIMATION algorithms FRAGMENT ASSEMBLY SEQUENCE RECONSTRUCTION

来源：评论

学校读者我要写书评

暂无评论

Some applications of a polynomial inequality to global optimization

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 2005年第1期127卷 193-205页

作者： Zhang, JF Kwong, CP Chinese Univ Hong Kong Dept Automat & Comp Aided Engn Shatin Hong Kong Peoples R China

In this paper, we use the Ehlich-Zeller-Gartel inequality to derive an algorithm for finding the global minima of polynomials over hyperrectangles as well as to provide a bounding method for the branch-and-bound algorithm. The latter application of the inequality results in an improved algorithm which gives simultaneously a decreasing upper bound and an increasing lower bound for the global minimum at each iteration. The algorithm can be used also to find the Lipschitz constant of a polynomial.

关键词： Ehlich-Zeller-Gartel inequality Lipschitz optimization branch-and-bound algorithms polynomials

来源：评论

学校读者我要写书评

暂无评论

EXACT AND APPROXIMATION algorithms FOR SORTING BY REVERSALS, WITH APPLICATION TO GENOME REARRANGEMENT

引用

ALGORITHMICA 1995年第1-2期13卷 180-210页

作者： KECECIOGLU, J SANKOFF, D UNIV MONTREAL CTR RECH MATHMONTREAL H3C 3J7PQCANADA

Motivated by the problem in computational biology of reconstructing the series of chromosome inversions by which one organism evolved from another, we consider the problem of computing the shortest series of reversals that transform one permutation to another. The permutations describe the order of genes on corresponding chromosomes, and a reversal takes an arbitrary substring of elements, and reverses their order. For this problem, we develop two algorithms: a greedy approximation algorithm, that finds a solution provably close to optimal in O(n(2)) time and O(n) space for n-element permutations, and a branch-and-bound exact algorithm, that finds an optimal solution in O(mL(n, n)) time and O(n(2)) space, where m is the size of the branch-and-bound search tree, and L(n, n) is the time tc, solve a linear program of n variables and n constraints. The greedy algorithm is the first to come within a constant factor of the optimum;it guarantees a solution that uses no more than twice the minimum number of reversals. The lower and upper bounds of the branch-and-bound algorithm are a novel application of maximum-weight matchings, shortest paths, and linear programming. In a series of experiments, we study the performance of an implementation on random permutations, and permutations generated by random reversals. For permutations differing by k random reversals, we find that the average upper bound on reversal distance estimates k to within one reversal for k < 1/2n and n less than or equal to 100. For the difficult case of random permutations, we find that the average difference between the upper and lower bounds is less than three reversals for n less than or equal to 50. Due to the tightness of these bounds, we can solve, to optimality, problems on 30 elements in a few minutes of computer time. This approaches the scale of mitochondrial genomes.

关键词： COMPUTATIONAL BIOLOGY APPROXIMATION algorithms branch-and-bound algorithms EXPERIMENTAL ANALYSIS OF algorithms EDIT DISTANCE PERMUTATIONS SORTING BY REVERSALS CHROMOSOME INVERSIONS GENOME REARRANGEMENTS

来源：评论

学校读者我要写书评

暂无评论

The multidimensional 0-1 knapsack problem:: An overview

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2004年第1期155卷 1-21页

作者： Fréville, A Univ Valenciennes & Hainaut Cambresis Grp Rech Operat & Informat CNRS Lab Automat Mecan & Informat Ind & HumainesUMR 8 F-59313 Valenciennes France

The multidimensional 0-1 knapsack problem is one of the most well-known integer programming problems and has received wide attention from the operational research community during the last four decades. Although recent advances have made possible the solution of medium size instances, solving this NP-hard problem remains a very interesting challenge, especially when the number of constraints increases. This paper surveys the main results published in the literature. The focus is on the theoretical properties as well as approximate or exact solutions of this special 0-1 program. (C) 2003 Elsevier B.V. All rights reserved.

关键词： multidimensional 0-1 knapsack problem heuristics probabilistic and worst-case analysis surrogate duality preprocessing branch-and-bound algorithms

来源：评论

学校读者我要写书评

暂无评论

Discovering cis-regulatory modules by optimizing barbecues

引用

DISCRETE APPLIED MATHEMATICS 2009年第10期157卷 2458-2468页

作者： Mosig, Axel Biyikoglu, Tuerker Prohaska, Sonja J. Stadler, Peter F. Shanghai Inst Biol Sci CAS MPG Partner Inst Computat Biol Shanghai 200031 Peoples R China Max Planck Inst Math Sci D-04103 Leipzig Germany Isik Univ TR-34980 Istanbul Turkey Univ Vienna Dept Theoret Chem A-1090 Vienna Austria Univ Leipzig Bioinformat Grp Dept Comp Sci D-04107 Leipzig Germany Univ Leipzig Interdisciplinary Ctr Bioinformat D-04107 Leipzig Germany Santa Fe Inst Santa Fe NM 87501 USA Arizona State Univ Dept Biomed Informat Sch Comp & Informat Tempe AZ 85287 USA Fraunhofer Inst Zelltherapie & Immunol D-04103 Leipzig Germany

Gene expression in eukaryotic cells is regulated by a complex network of interactions, in which transcription factors and their binding sites on the genomic DNA play a determining role. As transcription factors rarely, if ever, act in isolation, binding sites of interacting factors are typically arranged in close proximity forming so-called cis-regulatory modules. Even when the individual binding sites are known, module discovery remains a hard combinatorial problem, which we formalize here as the Best Barbecue Problem. It asks for simultaneously stabbing a maximum number of differently colored intervals from K arrangements of colored intervals. This geometric problem turns out to be an elementary, yet previously unstudied combinatorial optimization problem of detecting common edges in a family of hypergraphs, a decision version of which we show here to be NP-complete. Due to its relevance in biological applications, we propose algorithmic variations that are suitable for the analysis of real data sets comprising either many sequences or many binding sites. Being based on set systems induced by interval arrangements, our problem setting generalizes to discovering patterns of co-localized itemsets in non-sequential objects that consist of corresponding arrangements or induce set systems of co-localized items. In fact, our optimization problem is a generalization of the popular concept of frequent itemset mining. (c) 2008 Elsevier B.V. All rights reserved.

关键词： Gene regulation cis-regulatory modules (CRMs) Best barbecue problem NP-completeness branch-and-bound algorithms Itemset mining

来源：评论

学校读者我要写书评

暂无评论

Creating a consensus ranking of proposals from reviewers' partial ordinal rankings

引用

COMPUTERS & OPERATIONS RESEARCH 2007年第4期34卷 954-965页

作者： Cook, Wade D. Golany, Boaz Penn, Michal Raviv, Tal York Univ Schulich Sch Buiness N York ON M3J 1P3 Canada Technion Israel Inst Technol Fac Ind Engn & Management IL-32000 Haifa Israel Univ British Columbia Sauder Sch Buiness Vancouver BC V6T 1Z2 Canada

Peer review of research proposals and articles is an essential element in R&D processes worldwide. In most cases, each reviewer evaluates a small subset of the candidate proposals. The review board is then faced with the challenge of creating an overall "consensus" ranking on the basis of many partial rankings. In this paper we propose a branch-and-bound model to support the construction of an aggregate ranking from the partial rankings provided by the reviewers. In a recent paper we proposed ways to allocate proposals to reviewers so as to achieve the maximum possible overlap among the subsets of proposals allocated to different reviewers. Here, we develop a special branch-and-bound algorithm that utilizes the overlap generated through our earlier methods to enable discrimination in ranking the competing proposals. The effectiveness and efficiency of the algorithm is demonstrated with small numerical examples and tested through an extensive simulation experiment. (c) 2005 Elsevier Ltd. All rights reserved.

关键词： peer review branch-and-bound algorithms

来源：评论

学校读者我要写书评

暂无评论

Heuristic rejection in interval global optimization

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 2003年第1期118卷 27-43页

作者： Casado, LG García, I Csendes, T Ruíz, VG Univ Almeria Dept Computer Architecture & Elect Almeria Spain Univ Szeged Inst Informat Szeged Hungary

Based on the investigation carried out in Ref. 1, this paper incorporates new studies about the properties of inclusion functions on subintervals while a branch-and-bound algorithm is solving global optimization problems. It is found that the relative place of the global minimum value within the inclusion function value of the objective function at the current interval indicates mostly whether the given interval is close to a minimizer point. This information is used in a heuristic interval rejection rule that can save a considerable amount of computation. Illustrative examples are discussed and an extended numerical study shows the advantages of the new approach.

关键词： interval method global optimization branch-and-bound algorithms

来源：评论

学校读者我要写书评

暂无评论

Exact and heuristic algorithms for parallel-machine scheduling with DeJong's learning effect

引用

COMPUTERS & INDUSTRIAL ENGINEERING 2010年第2期59卷 272-279页

作者： Okolowski, Dariusz Gawiejnowicz, Stanislaw Adam Mickiewicz Univ Poznan Fac Math & Comp Sci PL-61614 Poznan Poland

We consider a parallel-machine scheduling problem with a learning effect and the makespan objective. The impact of the learning effect on job processing times is modelled by the general DeJong's learning curve. For this NP-hard problem we propose two exact algorithms: a sequential branch-and-bound algorithm and a parallel branch-and-bound algorithm. We also present the results of experimental evaluation of these algorithms on a computational cluster. Finally, we use the exact algorithms to estimate the performance of two greedy heuristic scheduling algorithms for the problem. (c) 2010 Elsevier Ltd. All rights reserved.

关键词： Parallel-machine scheduling Learning effect branch-and-bound algorithms Heuristic scheduling algorithms

来源：评论

学校读者我要写书评

暂无评论

USING CONVEX ENVELOPES TO SOLVE THE INTERACTIVE FIXED-CHARGE LINEAR-PROGRAMMING PROBLEM

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 1988年第2期59卷 223-246页

作者： BENSON, HP ERENGUC, SS 1.Department of Decision and Information Sciences College of Business Administration University of Florida Gainesville Florida

In the well-known fixed-charge linear programming problem, it is assumed, for each activity, that the value of the fixed charge incurred when the level of the activity is positive does not depend upon which other activities, if any, are also undertaken at a positive level. However, we have encountered several practical problems where this assumption does not hold. In an earlier paper, we developed a new problem, called the interactive fixed-charge linear programming problem (IFCLP), to model these problems. In this paper, we show how to construct the convex envelopes and other convex underestimating functions for the objective function for problem (IFCLP) over various rectangular subsets of its domain. Using these results, we develop a specialized branch-and-bound algorithm for problem (IFCLP) which finds an exact optimal solution for the problem in a finite number of steps. We also discuss the main properties of this algorithm.

关键词： Fixed-charge problem interactive fixed-charge problem nonconvex programming convex envelopes branch-and-bound algorithms

来源：评论

学校读者我要写书评

暂无评论

RANGI: A Fast List-Colored Graph Motif Finding Algorithm

引用

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS 2013年第2期10卷 504-513页

作者： Rudi, Ali Gholami Shahrivari, Saeed Jalili, Saeed Kashani, Zahra Razaghi Moghadam Tarbiat Modares Univ Fac Elect & Comp Engn Tehran Iran

Given a multiset of colors as the query and a list-colored graph, i.e., an undirected graph with a set of colors assigned to each of its vertices, in the NP-hard list-colored graph motif problem the goal is to find the largest connected subgraph such that one can select a color from the set of colors assigned to each of its vertices to obtain a subset of the query. This problem was introduced to find functional motifs in biological networks. We present a branch-and-bound algorithm named RANGI for finding and enumerating list-colored graph motifs. As our experimental results show, RANGI's pruning methods and heuristics make it quite fast in practice compared to the algorithms presented in the literature. We also present a parallel version of RANGI that achieves acceptable scalability.

关键词： branch-and-bound algorithms parallel algorithms list-colored graphs protein-interaction networks

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：