Construction of Selection Indexes with Restrictions

In this paper the problem of unistage selection with inequality constraints is formulated. If the predictor and criterion variables are all normally distributed, this problem can be written as a convex programming problem, with a linear objective function and with linear constraints and a quadratic constraint. Using the duality theory, for convex nonlinear programming it is proved, that its dual problem can be transformed into a convex minimization problem with non-negativity conditions. Good computational methods are known for solving this problem. By the help of the dual problem sufficient conditions for a solution of the original primal problem are derived and illustrated by an example of practical interest.     

Pathocoenoses ancient and modern

Problems concerning the concept of biocoenosis in ecology (the antecedent of the pathocoenosis concept) are discussed first of all. Six main problems are identified: the problem of emergent properties of ecological communities; the problem of ambiguity; the problem of heterogeneity; the boundary problem; the problem of retrospective differential diagnosis; and the problem of explaining change over time. The rest of the paper gives illustrations of these problems in relation to human pathogens drawn mainly from the interactions of malaria with other diseases, particularly but not exclusively in the Mediterranean world, from antiquity through to modern times.     

An Omega(n2/ log n) speed-up of TBR heuristics for the gene-duplication problem

The gene-duplication problem is to infer a species supertree from gene trees that are confounded by complex histories of gene duplications. This problem is NP-hard and thus requires efficient and effective heuristics. Existing heuristics perform a stepwise search of the tree space, where each step is guided by an exact solution to an instance of a local search problem. We improve on the time complexity of the local search problem by a factor of n2= log n, where n is the size of the resulting species supertree. Typically, several thousand instances of the local search problem are solved throughout a stepwise heuristic search. Hence, our improvement makes the gene-duplication problem much more tractable for large-scale phylogenetic analyses.     

The Gene-Duplication Problem: Near-Linear Time Algorithms for NNI-Based Local Searches

The gene-duplication problem is to infer a species supertree from a collection of gene trees that are confounded by complex histories of gene-duplication events. This problem is NP-complete and thus requires efficient and effective heuristics. Existing heuristics perform a stepwise search of the tree space, where each step is guided by an exact solution to an instance of a local search problem. A classical local search problem is the {tt NNI} search problem, which is based on the nearest neighbor interchange operation. In this work, we 1) provide a novel near-linear time algorithm for the {tt NNI} search problem, 2) introduce extensions that significantly enlarge the search space of the {tt NNI} search problem, and 3) present algorithms for these extended versions that are asymptotically just as efficient as our algorithm for the {tt NNI} search problem. The exceptional speedup achieved in the extended {tt NNI} search problems makes the gene-duplication problem more tractable for large-scale phylogenetic analyses. We verify the performance of our algorithms in a comparison study using sets of large randomly generated gene trees.     

Predictive algorithms for neuromuscular control of human locomotion.

The problem of quantifying muscular activity of the human body can be formulated as an optimal control problem. The current methods used with large-scale biomechanical systems are non-derivative techniques. These methods are costly, as they require numerous integrations of the equations of motion. Additionally, the convergence is slow, making them impractical for use with large systems. We apply an efficient numerical algorithm to the biomechanical optimal control problem. Using direct collocation with a trapezoidal discretization, the equations of motion are converted into a set of algebraic constraint equations. An augmented Lagrangian formulation is used for the optimization problem to handle both equality and inequality constraints. The resulting min-max problem is solved with a generalized Newton method. In contrast to the prevalent optimal control implementations, we calculate analytical first- and second-derivative information and obtain local quadratic convergence. To demonstrate the efficacy of the method, we solve a steady-state pedaling problem with 7 segments and 18 independent muscle groups. The computed muscle activations compare well with experimental EMG data. The computational effort is significantly reduced and solution times are a fraction of those of the non-derivative techniques.     

An improved heuristic for haplotype inference

Haplotypes include essential SNP information used for a variety of purposes such as investigating potential links between certain diseases and genetic variations. Given a set of genotypes, the haplotype inference problem based on pure parsimony is the problem of finding a minimum set of haplotypes that explains all the given genotypes. The problem is especially important because, while it is fairly inexpensive to obtain genotypes, other approaches to obtaining haplotypes are significantly expensive. There are two types of methods proposed for the problem, namely exact and inexact methods. Existing exact methods guarantee obtaining purely parsimonious solutions but have exponential time-complexities and are not practical for large number or length of genotypes. However, inexact methods are relatively fast but do not always obtain optimum solutions. In this paper, an improved heuristic is proposed, based on which new inexact and exact methods are provided. Experimental results indicate that the proposed methods replace the state-of-the-art inexact and exact methods for the problem.     

Multiple sequence assembly from reads alignable to a common reference genome

We describe a set of computational problems motivated by certain analysis tasks in genome resequencing. These are assembly problems for which multiple distinct sequences must be assembled, but where the relative positions of reads to be assembled are already known. This information is obtained from a common reference genome and is characteristic of resequencing experiments. The simplest variant of the problem aims at determining a minimum set of superstrings such that each sequenced read matches at least one superstring. We give an algorithm with time complexity O(N), where N is the sum of the lengths of reads, substantially improving on previous algorithms for solving the same problem. We also examine the problem of finding the smallest number of reads to remove such that the remaining reads are consistent with k superstrings. By exploiting a surprising relationship with the minimum cost flow problem, we show that this problem can be solved in polynomial time when nested reads are excluded. If nested reads are permitted, this problem of removing the minimum number of reads becomes NP-hard. We show that permitting mismatches between reads and their nearest superstrings generally renders these problems NP-hard.     

The component retrieval problem in printed circuit board assembly

Minimization of the makespan of a printed circuit board assembly process is a complex problem. Decisions involved in this problem concern the specification of the order in which components are to be placed on the board and the assignment of component types to the feeder slots of the placement machine. If some component types are assigned to multiple feeder slots, an additional problem emerges: for each placement on the board, one must select the feeder slot from which the required component is to be retrieved. In this paper, we consider this component retrieval problem for placement machines of the Fuji CP type. We explain why simple forward dynamic programming schemes cannot provide a solution to this problem, invalidating the correctness of an algorithm proposed by Bard, Clayton, and Feo (1994). We then present a polynomial algorithm that solves the problem to optimality. The analysis of the component retrieval problem is facilitated by its reformulation as a PERT/CPM problem with design aspects: finding the minimal makespan of the assembly process amounts to identifying a design for which the longest path in the induced PERT/CPM network is shortest. The complexity of this network problem is analyzed, and we prove that the polynomial solvability of the component retrieval problem is caused by the specific structure it inflicts on the arc lengths of the network: in the absence of this structure, the network problem is shown to be NP-hard.     

Exact algorithms for planted motif problems.

The problem of identifying meaningful patterns (i.e., motifs) from biological data has been studied extensively due to its paramount importance. Three versions of this problem have been identified in the literature. One of these three problems is the planted (l, d)-motif problem. Several instances of this problem have been posed as a challenge. Numerous algorithms have been proposed in the literature that address this challenge. Many of these algorithms fall under the category of heuristic algorithms. In this paper we present algorithms for the planted (l, d)-motif problem that always find the correct answer(s). Our algorithms are very simple and are based on some ideas that are fundamentally different from the ones employed in the literature. We believe that the techniques we introduce in this paper will find independent applications.     

Sea-lice infection models for fishes

As free-living sea-lice larvae are difficult to sample directly, lice abundances on fish have recently been used to study larvae in the water. In the KLV problem, juvenile wild salmon migrate past a salmon farm, and the change of infection with distance along the migration route is used to estimate larvae production from the farm. In the farm problem, time-varying infection of sea-cage fish is used to estimate the time-variation of free-living larvae in waters near the farm. Both inverse problems require good forward models for infection. In the farm problem, hosts are relatively large and lice pathogenesis is seldom mortal, whereas in the KLV problem hosts are small and lice-induced host mortality can affect lice abundance; thus, infection models for the farm problem are special cases of models for the KLV problem. Here I give an infection model for the KLV problem that explicitly includes lice clumping and host mortality, showing that Krkosek et al. (Proc R Soc B 272:689-696, 2005) (KLV) probably underestimated larvae production by the salmon farm, and further, that if lice development rates were known from laboratory data, lice abundance field data could be directly inverted for lice-induced host mortality during migration. If lice-induced host mortality is negligible, or if lice are Poisson distributed, infection models of arbitrary complexity reduce to Erlang models. I give two useful Erlang models with their solutions for non-zero initial conditions.     

Pontryagin's principle for control problems in age-dependent population dynamics

In this paper, Pontryagin's principle is proved for a fairly general problem of optimal control of populations with continuous time and age variable. As a consequence, maximum principles are developed for an optimal harvesting problem and a problem of optimal birth control.     

On the statistical distribution of mutant bacteria

A problem in probability is stated with included the problem of the distribution of bacterial mutants as a special case. This problem is solved exactly but since the resulting expressions are too complicated for practical use, various approximate expressions for the distribution are considered, especially for the bacterial mutation case. Research sponsored by the Office of Naval Research while the author was at the California Institute of Technology.     

The numerical method for the optimal supporting position and related optimal control for the catalytic reaction system

This paper considers the numerical approximation for the optimal supporting position and related optimal control of a catalytic reaction system with some control and state constraints, which is governed by a nonlinear partial differential equations with given initial and boundary conditions. By the Galerkin finite element method, the original problem is projected into a semi-discrete optimal control problem governed by a system of ordinary differential equations. Then the control parameterization method is applied to approximate the control and reduce the original system to an optimal parameter selection problem, in which both the position and related control are taken as decision variables to be optimized. This problem can be solved as a nonlinear optimization problem by a particle swarm optimization algorithm. The numerical simulations are given to illustrate the effectiveness of the proposed numerical approximation method.     

Exemplar longest common subsequence

In this paper, we investigate the computational and approximation complexity of the Exemplar Longest Common Subsequence of a set of sequences (ELCS problem), a generalization of the Longest Common Subsequence problem, where the input sequences are over the union of two disjoint sets of symbols, a set of mandatory symbols and a set of optional symbols. We show that different versions of the problem are APX-hard even for instances with two sequences. Moreover, we show that the related problem of determining the existence of a feasible solution of the Exemplar Longest Common Subsequence of two sequences is NP-hard. On the positive side, we first present an efficient algorithm for the ELCS problem over instances of two sequences where each mandatory symbol can appear in total at most three times in the sequences. Furthermore, we present two fixed-parameter algorithms for the ELCS problem over instances of two sequences where the parameter is the number of mandatory symbols.     

Modelling the effect of immigration on drinking behaviour

A drinking model with immigration is constructed. For the model with problem drinking immigration, the model admits only one problem drinking equilibrium. For the model without problem drinking immigration, the model has two equilibria, one is problem drinking-free equilibrium and the other is problem drinking equilibrium. By employing the method of Lyapunov function, stability of all kinds of equilibria is obtained. Numerical simulations are also provided to illustrate our analytical results. Our results show that alcohol immigrants increase the difficulty of the temperance work of the region.     

The value of information in reserve site selection

The reserve site selection problem is to select sites for the establishment of biological reserves with the goal to maximize the number of species contained in the reserves. When species distributions are known, this corresponds to the maximal coverage problem. In practice, knowledge of species distributions may be incomplete and only incidence probabilities are available. In this case, the goal is to maximize the expected number of species contained in the reserves. This is called the maximal expected coverage problem. This paper describes and illustrates a formal approach to assess the value of information, such as site surveys or species surveys, in this problem.     

PCB assembly scheduling with alternative nozzle types for one component type

The placement machine is the bottleneck of a printed circuit board (PCB) assembly line. The type of machine considered in this paper is the beam-type placement machine that can simultaneously pick up several components from feeders. It is assumed that the number of nozzle types (NTs) is less than the number of heads on the beam. The objective of the PCB assembly scheduling for a single placement machine is to minimize the cycle time based on the average machine operation time instead of the travelling distance. To minimize the cycle time, the number of turns and the number of pickups should be minimized. The PCB assembly scheduling is hierarchically decomposed into four problems: the nozzle assignment problem, the head allocation problem, the component type (CT) grouping problem and the pickup clustering problem, which are optimized successively and iteratively. First, the nozzle assignment problem considering alternative NTs for one CT is dealt with by the proposed genetic algorithm. For a given nozzle assignment solution, the head allocation problem is solved by a previously greedy heuristic to minimize the number of turns.Then, the CT grouping problem and the pickup clustering problem are solved by a proposed greedy heuristic and a modified agglomerative hierarchical clustering approach, respectively, to minimize the number of pickups. Numerical experiments are carried out to examine the performances of these proposed heuristic approaches. The importance of considering alternative NTs for one CT for the cycle time is also confirmed.     

The paradox of magnetobiology: analysis and prospects for solution

The wording, content, and corollaries of the so-called "kT problem" are considered. The problem points to the paradox of the biological effects of weak low-frequency magnetic fields. The conventional wording of the problem contains implicit assumptions the analysis of which shows their incomplete physical validity.     

Analysis of mussel growth data*

This short paper considers the problem of estimating the year of birth of a mussel picked at an unknown time. This is an important problem not only for studying a certain mussel population but also for environmental monitoring. A mathematical formulation of the problem is presented, which leads to a combined delay estimation and constrained linear regression problem. A solution is developed and applied to the estimation problem. Examples with mussels picked from a river in Sweden are shown, which demonstrate that the proposed technique works well in practice.