1,721,010 research outputs found
Resource-constrained Machine Scheduling
No full textBackground Scheduling is a form of decision-making that plays a very importantrole in manufacturing industries. It is the method by which workgets assigned to resources that compute it. In this thesis we want to assignjobs (cycles of a lithography process) to different machines in such a waythat the machines are running for as little time as possible. The difficultylies in the fact that some jobs require the same resource, and thus cannotbe processed simultaneously.Results It appears that the following scheduling problems are NP-hard:• P2kCmax and R2kCmax• P3|res · 11, pj = 1|Cmax and R3|res · 11, pj = 1|Cmax• P3|res · 11, pj = 1|P Cj and R3|res · 11, pj = 1|P CjWe try to approximate an optimal solution for the scheduling problemRm|res · 11|P Cj by calculating a ratio with a lower bound, where we ignoreresource constraints, and an upper bound, that is found by a Greedyalgorithm (w.r.t. resource constraints).Conclusions It appears that Greedy is not a very good approximationalgorithm for this problem, since the ratio in which the optimal TotalCompletion Time should lie is about 8,33% of the average calculated TotalCompletion Tim
Measuring how far a nonbinary phylogenetic network is from being tree-based
No full textIn computational biology, phylogenetic trees are used to describe evolutionary history. This can be done more generally using phylogenetic networks, which can also describe nontreelike events such as hybridization. Some phylogenetic networks can be obtained from a base tree, a rooted spanning tree with the same leaf set, by adding linking edges. Such networks are called tree-based. In recent articles, characterizations of binary tree-based networks are given. They are linked to maximum-sized matchings in bipartite graphs, path partitions and antichains. However, in many real-life applications, phylogenetic networks are not binary. Therefore, we will prove that some characterizations are extendable to all (nonbinary) phylogenetic networks while some others are not. We will discuss five proximity measures of how close an arbitrarily (nonbinary) phylogenetic network is to being tree-based. Three of the measures turn out to be equal and at least three of them are computable in polynomial time. We show that this is also true in the nonbinary case. Lastly, we prove two inequalities comparing the other measures
Multi-robot parcel sorting systems: Allocation and path finding
No full textThe logistics industry is being modernized using information technology and robots. This change encompasses a new set of challenges in warehouses. Recently, some companies have started using robot fleets to sort products and parcels. This thesis studies those systems, and researches the combinatorial problems that arise within them. Three main optimization problems are identified: 1. Finding an optimal layout of the sorting system on the warehouse floor; 2. Allocating products or parcels to be sorted to robots; 3. Finding paths that all robots can follow concurrently, without colliding. These problems are considered one by one. The first problem is understood on an intuitive level, while the other two are considered more closely. For both problems, several algorithms are considered. Some utilize greedy heuristics while others model the problem at hand precisely using integer linear programming methods. The algorithm’s real world performance is then assessed using a simulation. Slow, ILP-based algorithms are found to produce optimal solutions for small instances. However, they don’t scale well, and are unable to solve large instances. Greedy approximation algorithms solve all problem instance sizes tested, but produce solutions of lower quality.Applied Mathematic
Preventing overfitting in Mixed Integer Optimization based classification tree construction
No full textThe global use of azole antifungals as treatment against infections caused by Candida has led to an increase in azole resistance. The primal goal of this BSc thesis is to improve existing Mixed Integer Optimization models to classify azole resistance of C. glabrata more accurately by preventing overfitting. Moreover, these classification methods can generally also be used for the classification of any kind of numerical of categorical data. The classification method that we used is based on an MIO formulation that was first introduced by Bertsimas and Dunn, and later adapted by Van Dijk. We first made the output of the model much easier to interpret, both from a mathematical and biological point of view. We also applied feature sampling to reduce the run time of the program, making it possible to create deeper trees, and to prevent overfitting. To further prevent overfitting in these deeper trees, we added the option of forcing at least a certain number of training data points in the leaves to the MIO formulation. We verified our MIO model on a data set constructed by combining two data sets from the Westerdijk Fungal Biodiversity institute and a data set from the Center for Disease Control and Prevention Atlanta, all containing the FKS1 and FKS2 gene sequences from C. Glabrata. We automated the preprocessing steps and merging process of these data sets with a Python program, and wrote a user manual on how to use this program. By processing a bigger data set we were able to classify more data correctly than Van Dijk, and we outperformed the CART algorithm. Similar accuracy results were obtained when applying feature sampling as when not, and the run time was drastically reduced. Deeper trees did not change out-of-sample accuracy much, though this may be because our data sets did not require deeper trees. When also forcing at least a certain number of training data points in each leaf of these deeper trees, we were able to slightly increase the out-of-sample accuracy, which means overfitting was indeed prevented slightly. Lastly we interpreted the results in biological context, and found some resistance-related mutations that were already identified previously in other research, as well as some additional ones for which the biological relevance is yet unknown.Applied Mathematic
Parental Parsimony on Phylogenetic Networks: Computing the Maximum Parsimony Scores of Phylogenetic Networks
No full textPhylogenetic networks represent the evolutionary history of organisms and the relationships among them. In the field of phylogenetics research has been done to reconstruct these networks. Several methods for reconstructing those networks have been developed over the years. One of them is the softwired parsimony score and another, a fairly new method, is the parental parsimony method. In theory this is a better and more accurate method, but before this thesis, it was not tested yet. In this thesis, we compare the softwired and the parental parsimony method in practice by implementing the methods and calculating their parsimony scores. The results will show that the parental parsimony is a better and more accurate method in practice as well
New FPT algorithms for finding the temporal hybridization number for sets of phylogenetic trees
No full textWe study the problem of finding a temporal hybridization network for a set of phylogenetic trees that minimizes the number of reticulations. First, we introduce an FPT algorithm for this problem on an arbitrary set of t binary trees with n leaves each with a running time of O(5^k*n*m) where k is the minimum temporal hybridization number. We also present the concept of temporal distance, which is a measure for how close a tree-child network is to being temporal. Then we introduce an algorithm for computing a tree-child network with temporal distance at most p and at most k reticulations in O((8k)^p*5^k*n*m). Lastly, we introduce a O(6^k*k!*n) algorithm for computing a minimum temporal hybridization network for a set of two nonbinary trees
Constructing level-2 phylogenetic networks from trinets
No full textPhylogenetic networks are a generalization of evolutionary trees that can be used to represent reticulate events. Level-k phylogenetic networks are such networks, but with a at most k reticulations per biconnected component of the network. For level-1 networks there exists an algorithm, called TriLoNet (Trinet Level-one Network algorithm), that constructs these networks directly from sequence alignments which works by piecing together smaller level-1 networks on three taxa. Here, we introduce TriL2Net (Trinet Level-2 Network algorithm), an algorithm similar to TriLoNet that works for the larger class of level-2 networks. More specifically, TriL2Net constructs a level-2 phylogenetic network from a set of level-2 trinets. We show that TriL2Net performs better on sampled level-2 networks than TriLoNet performs om sampled level-1 networks. We hypothesize that this result is either due to the different ways the data is sampled, or the difference in heuristics used. Moreover, we applied TriL2Net to level-1 trinet sets derived from real sequence data involving recombination. When comparing the networks generated by TriL2Net from these data sets to the networks generated by TriLoNet from these same data sets, we found that TriL2Net’s networks are at least as consistent with the input as TriLoNet’s networks. TriL2Net has been implemented in Python and is freely available at https://github.com/KSjors/TriL2Net.Applied Mathematic
Who Should Have a Place on the Ark? Parameterized algorithms for the maximization of the Phylogenetic Diversity
Full text linkPhylogenetic Diversity (PD) is a well-regarded measure of the overall biodiversity of a set of present-day species (taxa) that indicates its ecological signiőcance. In the Maximize Phylogenetic Diversity (Max-PD) roblem one is asked to őnd a small set of taxa in a phylogenetic tree for which this measure is maximized. Max-PD is particularly relevant in conservation planning, where limited resources necessitate prioritizing certain taxa to minimize biodiversity loss. Although Max-PD can be solved in polynomial time [Steel, Systematic Biology, 2005; Pardi and Goldman, PLoS Genetics, 2005], its generalizationsÐwhich aim to model biological processes and other aspects in conservation planning with greater accuracyÐoften exhibit NP-hardness, making them computationally challenging. This thesis explores a selection of these generalized problems within the framework of parameterized complexity. In Generalized Noah’s Ark Problem (GNAP), each taxon only survives at a certain survival probability, which can be increased by investing more money in the taxon. We show that GNAP is W[1]-hard with respect to the number of taxa but is XP with respect to the number of different costs and different survival probabilities. Additionally, we show that unit-cost-NAP, a special case of GNAP, is NP-hard. In Time Sensitive Maximization of Phylogenetic Diversity (Time-PD), different extinction times of taxa are considered after which they can no longer be saved. For Time-PD, we present color-coding algorithms that prove that Time-PD is őxed-parameter tractable (FPT) with respect to the threshold of diversity and the acceptable loss of diversity. In Optimizing PD with Dependencies (PDD), each saved taxon must be a source in the ecological system or a predator of another saved species. These dependencies are given in a food-web. We show that PDD is FPT when parameterized with the size of the solution plus the height of the phylogenetic tree. Further, we consider parameters characterizing the food-web and prove that PDD is FPT with respect to the treewidth if the phylogenetic tree is a star, disproving an open conjecture. Phylogenetic Diversity is traditionally deőned on phylogenetic trees, but phylogenetic networks have gained popularity as they enable the modeling of so-called reticulation events. Max-All-Paths-PD (MapPD) and Max-Net-PD are two problems in maximizing phylogenetic diversity on phylogenetic networks. MapPD is W[2]-hard with respect to the solution size but we show that MapPD is FPT with respect to the number of reticulations and the treewidth, two parameters that show how tree-like the phylogenetic network is. Max-Net-PD however remains NP-hard even on level-1-networks
Parallel Machine Scheduling: with Partition Constraints
No full textApplied Mathematics | Optimizatio
Computing Measures for Tree-Basedness of Phylogenetic Networks
No full textPhylogenetic networks are a type of directed acyclic graph used to represent evolutionary relationships that contain events such as hybridization or horizontal gene transfer. When a networklacks such events it is a phylogenetic tree. Some phylogenetic networks that are not trees canhowever be represented as a tree with additional linking arcs, e.g. representing transfer of geneticmaterials. We have implemented an algorithm that can be used to determine whether a givennetwork is tree-based or not. Moreover if the network is not tree-based, the algorithm showshow it can be made tree-based by adding a minimum number of additional leaves, representingpossible extinct or un-sampled species. We also describe the theory behind the algorithm andapply it to several synthetic as well as biological datasets
- …
