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

A property preserving method for extending a single-objective problem instance to multiple objectives with specific correlations 16th

学校读者我要写书评

暂无评论

A property preserving method for extending a single-objectiv...

16th European Conference on Evolutionary Computation in Combinatorial Optimization, EvoCOP 2016

作者： Moritz, Ruby L.V. Reich, Enrico Bernt, Matthias Middendorf, Martin Intelligent Systems Group Otto-von-Guericke University Magdeburg Magdeburg Germany Parallel Computing and Complex Systems Group Institute of Computer Science University of Leipzig Leipzig Germany

ISBN: (纸本)9783319306971

A method is proposed to generate multi-objective optimization problem instances from a corresponding single-objective instance. The user of the method can specify the correlations between the generated the objectives. Different from existing instance generation methods the new method allows to keep certain properties of the original single-objective instance. In particular, we consider optimization problems where the objective is defined by a matrix, e.g., a distance matrix for the Traveling Salesperson problem (TSP) or a flow matrix for the Quadratic Assignment problem. It is shown that the method creates new distance matrices with specific correlations between each other and also have the same average distance and variance of distances as the distance matrix of the original instance. This property is important, e.g., when the influence of correlations between the objectives on the behavior of metaheuristics for the multi-objective TSP are investigated. Some properties of the new method are shown theoretically. In an empirical analysis the new method is compared with instance generation methods from the literature. © Springer International Publishing Switzerland 2016.

关键词： Multiobjective optimization

Forbidden time travel: Characterization of time-consistent tree reconciliation maps 17

学校读者我要写书评

暂无评论

Forbidden time travel: Characterization of time-consistent t...

17th International Workshop on Algorithms in Bioinformatics, WABI 2017

作者： Nøjgaard, Nikolai Geiß, Manuela Merkle, Daniel Stadler, Peter F. Wieseke, Nicolas Hellmuth, Marc Department of Mathematics and Computer Science University of Greifswald Greifswald Germany Department of Mathematics and Computer Science University of Southern Denmark Denmark Bioinformatics Group Department of Computer Science Interdisciplinary Center of Bioinformatics University of Leipzig Leipzig Germany Max-Planck-Institute for Mathematics in the Sciences Leipzig Germany Institute for Theoretical Chemistry University of Vienna Vienna Austria Santa Fe Institute Santa FeNM United States Parallel Computing and Complex Systems Group Department of Computer Science Leipzig University Leipzig Germany Saarland University Center for Bioinformatics Saarbrücken Germany

ISBN: (纸本)9783959770507

Motivation: In the absence of horizontal gene transfer it is possible to reconstruct the history of gene families from empirically determined orthology relations, which are equivalent to eventlabeled gene trees. Knowledge of the event labels considerably simplifies the problem of reconciling a gene tree T with a species trees S, relative to the reconciliation problem without prior knowledge of the event types. It is well-known that optimal reconciliations in the unlabeled case may violate time-consistency and thus are not biologically feasible. Here we investigate the mathematical structure of the event labeled reconciliation problem with horizontal transfer. Results: We investigate the issue of time-consistency for the event-labeled version of the reconciliation problem, provide a convenient axiomatic framework, and derive a complete characterization of time-consistent reconciliations. This characterization depends on certain weak conditions on the event-labeled gene trees that reflect conditions under which evolutionary events are observable at least in principle. We give an O(|V (T)| log(|V (S)|))-time algorithm to decide whether a time-consistent reconciliation map exists. It does not require the construction of explicit timing maps, but relies entirely on the comparably easy task of checking whether a small auxiliary graph is acyclic. Significance: The combinatorial characterization of time consistency and thus biologically feasible reconciliation is an important step towards the inference of gene family histories with horizontal transfer from orthology data, i.e., without presupposed gene and species trees. The fast algorithm to decide time consistency is useful in a broader context because it constitutes an attractive component for all tools that address tree reconciliation problems. © Nikolai Nøjgaard, Manuela Geiß, Daniel Merkle, Peter F. Stadler, Nicolas Wieseke, and Marc Hellmuth.

关键词： Genes

ILP-based modulo scheduling for high-level synthesis

学校读者我要写书评

暂无评论

ILP-based modulo scheduling for high-level synthesis

Proceedings of the International Conference on Compilers, Architectures and Synthesis for Embedded systems (CASES)

作者： Julian Oppermann Andreas Koch Melanie Reuter-Oppermann Oliver Sinnen Embedded Systems and Applications Group Technische Universität Darmstadt Germany Discrete Optimization and Logistics Group Karlsruhe Institute of Technology Germany Parallel and Reconfigurable Computing Group University of Auckland New Zealand

ISBN: (纸本)9781509035892

In high-level synthesis, loop pipelining is a technique to improve the throughput and utilisation of hardware datapaths by starting new loop iterations after a fixed amount of time, called the initiation interval (II), allowing to overlap subsequent iterations. The problem is to find the smallest II and corresponding operation schedule that fulfils all data dependencies and resource constraints, both of which are usually found by modulo scheduling. We propose Moovac1, a novel integer linear program (ILP) formulation of the modulo scheduling problem based on overlap variables to model exact resource constraints. Given enough time, Moovac will find a mimimum-II solution. This is in contrast to Canis' state-of-the-art Modulo SDC approach, which requires heuristic simplifications of the resource constraints. Moovac can thus be used as a reference to evaluate heuristics, or in a time-limited mode as a heuristic itself to provide a best-so-far solution. We schedule kernels from the CHStone and MachSuite benchmarks for loop pipelining with Moovac, Modulo SDC and a prior exact formulation by Eichenberger. Moovac has competitive performance in its time-limited mode, and delivers better results faster than the Modulo SDC scheduler for some loops. Often its structure leads to quicker solution times than Eichenberger's formulation. Using the Moovac-computed optimal solutions as a reference, we can confirm that the Modulo SDC heuristic is indeed capable of finding optimal or near-optimal solutions for the majority of smallto medium-sized loops. However, for larger loops the two algorithms begin to diverge, with Moovac often being significantly faster to prove the infeasibility of a candidate II. This can be exploited by running both schedulers synergistically, leading to a quicker convergence to the final II.

关键词： Schedules Pipeline processing Hardware Clocks Digital signal processing VLIW

On the impact of synchronizing clocks and processes on benchmarking MPI collectives 15

学校读者我要写书评

暂无评论

On the impact of synchronizing clocks and processes on bench...

22nd European MPI Users' group Meeting, EuroMPI 2015

作者： Hunold, Sascha Carpen-Amarie, Alexandra Institute of Information Systems Research Group for Parallel Computing Faculty of Informatics Vienna University of Technology Austria

ISBN: (纸本)9781450337953

We consider the problem of accurately measuring the time to complete an MPI collective operation, as the result strongly depends on how the time is measured. Our goal is to develop an experimental method that allows for reproducible measurements of MPI collectives. When executing large parallel codes, MPI processes are often skewed in time when entering a collective operation. However, to obtain reproducible measurements, it is a common approach to synchronize all processes before they call the MPI collective operation. We therefore take a closer look at two commonly used process synchronization schemes: (1) relying on MPIBarrier or (2) applying a window-based scheme using a common global time. We analyze both schemes experimentally and show the strengths and weaknesses of each approach. As window-based schemes require the notion of global time, we thoroughly evaluate different clock synchronization algorithms in various experiments. We also propose a novel clock synchronization algorithm that combines two advantages of known algorithms, which are (1) taking the inherent clock drift into account and (2) using a tree-based synchronization scheme to reduce the synchronization duration. © 2015 ACM.

关键词： Benchmarking

From event labeled gene trees to species trees

学校读者我要写书评

暂无评论

arXiv 2017年

作者： Hernandez-Rosales, Maribel Hellmuth, Marc Wieseke, Nicolas Huber, Katharina T. Moulton, Vincent Stadler, Peter F. Dpt. of Mathematics and Computer Science University of Greifswald Walther- Rathenau-Strasse 47 GreifswaldD-17487 Saarland University Center for Bioinformatics Building e 2.1 P.O. Box 151150 SaarbrückenD-66041 Bioinformatics Group Department of Computer Science Interdisciplinary Center of Bioinformatics University of Leipzig Härtelstraße 16-18 LeipzigD-04107 Germany School of Computing Sciences University of East Anglia NorwichNR4 7TJ United Kingdom Max-Planck-Institute for Mathematics in the Sciences Inselstraße 22 LeipzigD-04103 Germany Inst. F. Theoretical Chemistry University of Vienna Währingerstraße 17 WienA-1090 Austria Santa Fe Institute 1399 Hyde Park Rd. Santa Fe United States Parallel Computing and Complex Systems Group Department of Computer Science Leipzig University Augustusplatz 10 Leipzig04109 Germany

Background: Tree reconciliation problems have long been studied in phylogenetics. A particular variant of the reconciliation problem for a gene tree T and a species tree S assumes that for each interior vertex x of T it is known whether x represents a speciation or a duplication. This problem appears in the context of analyzing orthology data. Results: We show that S is a species tree for T if and only if S displays all rooted triples of T that have three distinct species as their leaves and are rooted in a speciation vertex. A valid reconciliation map can then be found in polynomial time. Simulated data shows that the event-labeled gene trees convey a large amount of information on underlying species trees, even for a large percentage of losses. Conclusions: The knowledge of event labels in a gene tree strongly constrains the possible species tree and, for a given species tree, also the possible reconciliation maps. Nevertheless, many degrees of freedom remain in the space of feasible solutions. In order to disambiguate the alternative solutions additional external constraints as well as optimization criteria could be employed. Copyright © 2017, The Authors. All rights reserved.

关键词： Polynomial approximation

Forbidden time travel: Characterization of time-consistent tree reconciliation maps

学校读者我要写书评

暂无评论

arXiv 2017年

作者： Nøjgaard, Nikolai Geiß, Manuela Stadler, Peter F. Merkle, Daniel Wieseke, Nicolas Hellmuth, Marc Dpt. of Mathematics and Computer Science University of Greifswald Walther- Rathenau-Strasse 47 GreifswaldD-17487 Saarland University Center for Bioinformatics Building e 2.1 P.O. Box 151150 SaarbrückenD-66041 Bioinformatics Group Department of Computer Science Interdisciplinary Center of Bioinformatics University of Leipzig Härtelstraße 16-18 LeipzigD-04107 Germany Department of Mathematics and Computer Science University of Southern Denmark Max-Planck-Institute for Mathematics in the Sciences Inselstraße 22 LeipzigD-04103 Germany Inst. F. Theoretical Chemistry University of Vienna Währingerstraße 17 WienA-1090 Austria Santa Fe Institute 1399 Hyde Park Rd. Santa Fe United States Parallel Computing and Complex Systems Group Department of Computer Science Leipzig University Augustusplatz 10 Leipzig04109 Germany

Motivation: In the absence of horizontal gene transfer it is possible to reconstruct the history of gene families from empirically determined orthology relations, which are equivalent to eventlabeled gene trees. Knowledge of the event labels considerably simplifies the problem of reconciling a gene tree T with a species trees S, relative to the reconciliation problem without prior knowledge of the event types. It is well-known that optimal reconciliations in the unlabeled case may violate time-consistency and thus are not biologically feasible. Here we investigate the mathematical structure of the event labeled reconciliation problem with horizontal transfer. Results: We investigate the issue of time-consistency for the event-labeled version of the reconciliation problem, provide a convenient axiomatic framework, and derive a complete characterization of time-consistent reconciliations. This characterization depends on certain weak conditions on the event-labeled gene trees that reflect conditions under which evolutionary events are observable at least in principle. We give an O(|V(T)|log(|V (S)|))-time algorithm to decide whether a time-consistent reconciliation map exists. It does not require the construction of explicit timing maps, but relies entirely on the comparably easy task of checking whether a small auxiliary graph is acyclic. Significance: The combinatorial characterization of time consistency and thus biologically feasible reconciliation is an important step towards the inference of gene family histories with horizontal transfer from orthology data, i.e., without presupposed gene and species trees. The fast algorithm to decide time consistency is useful in a broader context because it constitutes an attractive component for all tools that address tree reconciliation problems. Copyright © 2017, The Authors. All rights reserved.

关键词： Genes

Reconstructing gene trees from Fitch's xenology relation

学校读者我要写书评

暂无评论

arXiv 2017年

作者： Geiß, Manuela Anders, John Stadler, Peter F. Wieseke, Nicolas Hellmuth, Marc Bioinformatics Group Department of Computer Science Interdisciplinary Center of Bioinformatics University of Leipzig Härtelstraße 16-18 LeipzigD-04107 Germany Dpt. of Mathematics and Computer Science University of Greifswald Walther- Rathenau-Strasse 47 GreifswaldD-17487 Germany Saarland University Center for Bioinformatics Building E 2.1 P.O. Box 151150 SaarbrückenD-66041 Germany Max-Planck-Institute for Mathematics in the Sciences Inselstraße 22 LeipzigD-04103 Germany Inst. f. Theoretical Chemistry University of Vienna Währingerstraße 17 WienA-1090 Austria Santa Fe Institute 1399 Hyde Park Rd. Santa Fe United States Parallel Computing and Complex Systems Group Department of Computer Science Leipzig University Augustusplatz 10 Leipzig04109 Germany

Two genes are xenologs in the sense of Fitch if they are separated by at least one horizontal gene transfer event. Horizonal gene transfer is asymmetric in the sense that the transferred copy is distinguished from the one that remains within the ancestral lineage. Hence xenology is more precisely thought of as a non-symmetric relation: y is xenologous to x if y has been horizontally transferred at least once since it diverged from the least common ancestor of x and y. We show that xenology relations are characterized by a small set of forbidden induced subgraphs on three vertices. Furthermore, each xenology relation can be derived from a unique least-resolved edge-labeled phylogenetic tree. We provide a linear-time algorithm for the recognition of xenology relations and for the construction of its least-resolved edge-labeled phylogenetic tree. The fact that being a xenology relation is a heritable graph property, finally has far-reaching consequences on approximation problems associated with xenology relations. Copyright © 2017, The Authors. All rights reserved.

关键词： Clustering algorithms

Selected Recent Applications of Sparse Grids

学校读者我要写书评

暂无评论

Numerical Mathematics(Theory,Methods and Applications) 2015年第1期8卷 47-77页

作者： Benjamin Peherstorfer Christoph Kowitz Dirk Pfluger Hans-Joachim Bungartz Scientific Computing Group Dept.of Computer ScienceBoltzmannstr.385748 GarchingGermany Institutefor Advanced Study Technische UniversitätMünchenLichtenbergstr.2a85748 GarchingGermany Institute for Parallel and Distributed Systems University of StuttgartUni-versitätsstr.3870569 StuttgartGermany

Sparse grids have become a versatile tool for a vast range of applications reaching from interpolation and numerical quadrature to data-driven problems and uncertainty *** review four selected real-world applications of sparse grids:financial product pricing with the Black-Scholes model,interactive explo-ration of simulation data with sparse-grid-based surrogate models,analysis of simu-lation data through sparse grid data mining methods,and stability investigations of plasma turbulence simulations.

关键词： Sparse grids hierarchical decomposition adaptivity combination technique

Cograph editing: Merging modules is equivalent to editing P4s

学校读者我要写书评

暂无评论

arXiv 2017年

作者： Fritz, Adrian Hellmuth, Marc Wieseke, Nicolas Stadler, Peter F. Computational Biology of Infection Research Helmholtz Centre for Infection Research Inhoffenstraße 7 BraunschweigD-38124 Germany University of Greifswald Dpt. of Mathematics and Computer Science Walther- Rathenau-Strasse 47 GreifswaldD-17487 Germany Saarland University Center for Bioinformatics Building e 2.1 P.O. Box 151150 SaarbrückenD-66041 Germany Parallel Computing and Complex Systems Group Department of Computer Science University of Leipzig Augustusplatz 10 LeipzigD-04109 Germany Bioinformatics Group Department of Computer Science Interdisciplinary Center of Bioinformatics University of Leipzig Härtelstraße 16-18 LeipzigD-04107 Germany Max-Planck-Institute for Mathematics in the Sciences Inselstraße 22 LeipzigD-04103 Germany Inst. F. Theoretical Chemistry University of Vienna Währingerstraße 17 WienA-1090 Austria Santa Fe Institute 1399 Hyde Park Rd. Santa FeNM87501 United States

The modular decomposition of a graph G = (V;E) does not contain prime modules if and only if G is a cograph, that is, if no quadruple of vertices induces a simple connected path P4. The cograph editing problem consists in inserting into and deleting from G a set F of edges so that H = (V,EΔF) is a cograph and |F| is minimum. This NP-hard combinatorial optimization problem has recently found applications, e.g., in the context of phylogenetics. Efficient heuristics are hence of practical importance. The simple characterization of cographs in terms of their modular decomposition suggests that instead of editing G one could operate directly on the modular decomposition. We show here that editing the induced P4s is equivalent to resolving prime modules by means of a suitable defined merge operation on the submodules. Moreover, we characterize so-called module-preserving edit sets and demonstrate that optimal pairwise sequences of module-preserving edit sets exist for every non-cograph. This eventually leads to an exact algorithm for the cograph editing problem. In addition, we provide two heuristics with time complexity O(|V|3), resp., O(|V|2). Copyright © 2017, The Authors. All rights reserved.

关键词： Graph theory