Novel evolutionary models and applications to sequence alignment problems

In this paper, we present a novel graph-theoretical approach for representing a wide variety of sequence analysis problems within a single model. The model allows incorporation of the operations “insertion”, “deletion”, and “substitution”, and various parameters such as relative distances and weights. Conceptually, we refer the problem as the minimum weight common mutated sequence (MWCMS) problem. The MWCMS model has many applications including multiple sequence alignment problem, the phylogenetic analysis, the DNA sequencing problem, and sequence comparison problem, which encompass a core set of very difficult problems in computational biology. Thus the model presented in this paper lays out a mathematical modeling framework that allows one to investigate theoretical and computational issues, and to forge new advances for these distinct, but related problems. Through the introduction of supernodes, and the multi-layer supergraph, we proved that MWCMS is -complete. Furthermore, it was shown that a conflict graph derived from the multi-layer supergraph has the property that a solution to the associated node-packing problem of the conflict graph corresponds to a solution of the MWCMS problem. In this case, we proved that when the number of input sequences is a constant, MWCMS is polynomial-time solvable. We also demonstrated that some well-known combinatorial problems can be viewed as special cases of the MWCMS problem. In particular, we presented theoretical results implied by the MWCMS theory for the minimum weight supersequence problem, the minimum weight superstring problem, and the longest common subsequence problem. Two integer programming formulations were presented and a simple yet elegant decomposition heuristic was introduced. The integer programming instances have proven to be computationally intensive. Consequently, research involving simultaneous column and row generation and parallel computing will be explored. The heuristic algorithm, introduced herein for multiple sequence alignment, overcomes the order-dependent drawbacks of many of the existing algorithms, and is capable of returning good sequence alignments within reasonable computational time. It is able to return the optimal alignment for multiple sequences of length less than 1500 base pairs within 30 minutes. Its algorithmic decomposition nature lends itself naturally for parallel distributed computing, and we continue to explore its flexibility and scalability in a massive parallel environment.     

Regular expression constrained sequence alignment

We introduce regular expression constrained sequence alignment as the problem of finding the maximum alignment score between given strings $S_1$ and $S_2$ over all alignments such that in these alignments there exists a segment where some substring $s_1$ of $S_1$ is aligned to some substring $s_2$ of $S_2$, and both $s_1$ and $s_2$ match a given regular expression R, i.e. $s_1,s_2\in L(R)$ where $L(R)$ is the regular language described by R. For complexity results we assume, without loss of generality, that $n=|S_1|⩾|m|=|S_2|$. A motivation for the problem is that protein sequences can be aligned in a way that known motifs guide the alignments. We present an $\mathrm{O}(nmr)$ time algorithm for the regular expression constrained sequence alignment problem where $r=\mathrm{O}(t^4)$, and t is the number of states of a nondeterministic finite automaton N that accepts $L(R)$. We use in our algorithm a nondeterministic weighted finite automaton M that we construct from N. M has $\mathrm{O}(t^2)$ states where the transition-weights are obtained from the given costs of edit operations, and state-weights correspond to optimum alignment scores we compute using the underlying dynamic programming solution for sequence alignment. If we are given a deterministic finite automaton D accepting $L(R)$ with $t_d$ states then our construction creates a deterministic finite automaton $M_d$ with $t_d^2$ states. In this case, our algorithm takes $\mathrm{O}(t_d^{2}nm)$ time. Using $M_d$ results in faster computation than using M when $t_d<t^2$. If we only want to compute the optimum score, the space required by our algorithm is $\mathrm{O}(t^{2}n)$ ($\mathrm{O}(t_d^{2}m)$ if we use a given $M_d$). If we also want to compute an optimal alignment then our algorithm uses $\mathrm{O}(t^{2}m+t^2|s_1||s_2|)$ space ($\mathrm{O}(t_d^{2}m+t_d^2|s_1||s_2|)$ space if we use a given $M_d$) where $s_1$ and $s_2$ are substrings of $S_1$ and $S_2$, respectively, $s_1,s_2\in L(R)$, and $s_1$ and $s_2$ are aligned together in the optimal alignment that we construct. We also show that our method generalizes for the case of the problem with affine gap penalties, and for finding optimal regular expression constrained local sequence alignments.     

Parametric multiple sequence alignment and phylogeny construction

Bounds are given on the size of the parameter-space decomposition induced by multiple sequence alignment problems where phylogenetic information may be given or inferred. It is shown that many of the usual formulations of these problems fall within the same integer parametric framework, implying that the number of distinct optima obtained as the parameters are varied across their ranges is polynomially bounded in the length and number of sequences.     

Measuring rank correlation coefficients between financial time series: A GARCH-copula based sequence alignment algorithm

This paper presents a novel four-stage algorithm for the measurement of the rank correlation coefficients between pairwise financial time series. In first stage returns of financial time series are fitted as skewed-t distributions by the generalized autoregressive conditional heteroscedasticity model. In the second stage, the joint probability density function (PDF) of the fitted skewed-t distributions is computed using the symmetrized Joe–Clayton copula. The joint PDF is then utilized as the scoring scheme for pairwise sequence alignment in the third stage. After solving the optimal sequence alignment problem using the dynamic programming method, we obtain the aligned pairs of the series. Finally, we compute the rank correlation coefficients of the aligned pairs in the fourth stage. To the best of our knowledge, the proposed algorithm is the first to use a sequence alignment technique to pair numerical financial time series directly, without initially transforming numerical values into symbols. Using practical financial data, the experiments illustrate the method and demonstrate the advantages of the proposed algorithm.     

约束线性方程组的解的有限逼近序列

该文中作者构造了一类有限的序列｛ｘ_ｊ｝用来逼近约束线性方程组 ＡＸ＝ｂ,Ｘ∈Ｔ的某个解,这里Ａ∈Ｒ~（ｍ×ｎ）,ｂ∈Ｒ~ｍ,Ｔ是Ｒ~ｎ的子空间．     

Constrained markov decision processes with compact state and action spaces: the average case

Constrained Markov decision processes with compact state and action spaces are studied under long-run average reward or cost criteria. By introducing a corresponding Lagrange function, a saddle-point theorem is given, by which the existence of a constrained optimal pair of initial state distribution and policy is shown. Also, under the hypothesis of Doeblin, the functional characterization of a constrained optimal policy is obtained     

Constrained Optimization: Projected Gradient Flows

We consider a dynamical system approach to solve finite-dimensional smooth optimization problems with a compact and connected feasible set. In fact, by the well-known technique of equalizing inequality constraints using quadratic slack variables, we transform a general optimization problem into an associated problem without inequality constraints in a higher-dimensional space. We compute the projected gradient for the latter problem and consider its projection on the feasible set in the original, lower-dimensional space. In this way, we obtain an ordinary differential equation in the original variables, which is specially adapted to treat inequality constraints (for the idea, see Jongen and Stein, Frontiers in Global Optimization, pp. 223–236, Kluwer Academic, Dordrecht, 2003). The article shows that the derived ordinary differential equation possesses the basic properties which make it appropriate to solve the underlying optimization problem: the longtime behavior of its trajectories becomes stationary, all singularities are critical points, and the stable singularities are exactly the local minima. Finally, we sketch two numerical methods based on our approach.     

带非线性不等式约束优化问题的信赖域算法

借助于KKT条件和NCP函数,提出了求解带非线性不等式约束优化问题的信赖域算法.该算法在每一步迭代时,不必求解带信赖域界的二次规划子问题,仅需求一线性方程组系统.在适当的假设条件下,它还是整体收敛的和局部超线性收敛的.数值实验结果表明该方法是有效的.     

A pattern sequence approach to Stern’s sequence

Suppose that w∈1{0,1}^∗ and let a_w(n) be the number of occurrences of the word w in the binary expansion of n. Let {s(n)}_n?0 denote the Stern sequence, defined by s(0)=0, s(1)=1, and for n?1, In this note, we show that where denotes the complement of w (obtained by sending 0?1 and 1?0) and [w]₂ denotes the integer specified by the word w∈{0,1}^∗ interpreted in base 2.     

Value Estimation Approach to the Iri-Imai Method for Constrained Convex Optimization

In this paper we propose an extension of the so-called Iri-Imai method to solve constrained convex programming problems. The original Iri-Imai method is designed for linear programs and assumes that the optimal objective value of the optimization problem is known in advance. Zhang (Ref. 9) extends the method for constrained convex optimization but the optimum value is still assumed to be known in advance. In our new extension this last requirement on the optimal value is relaxed; instead only a lower bound of the optimal value is needed. Our approach uses a multiplicative barrier function for the problem with a univariate parameter that represents an estimated optimum value of the original optimization problem. An optimal solution to the original problem can be traced down by minimizing the multiplicative barrier function. Due to the convexity of this barrier function the optimal objective value as well as the optimal solution of the original problem are sought iteratively by applying Newtons method to the multiplicative barrier function. A new formulation of the multiplicative barrier function is further developed to acquire computational tractability and efficiency. Numerical results are presented to show the efficiency of the new method.His research supported by Hong Kong RGC Earmarked Grant CUHK4233/01E.Communicated by Z. Q. Luo     

Aligning simulation models: A case study and results

This paper develops the concepts and methods of a process we will call “alignment of computational models” or “docking” for short. Alignment is needed to determine whether two models can produce the same results, which in turn is the basis for critical experiments and for tests of whether one model can subsume another. We illustrate our concepts and methods using as a target a model of cultural transmission built by Axelrod. For comparison we use the Sugarscape model developed by Epstein and Axtell. The two models differ in many ways and, to date, have been employed with quite different aims. The Axelrod model has been used principally for intensive experimentation with parameter variation, and includes only one mechanism. In contrast, the Sugarscape model has been used primarily to generate rich “artificial histories”, scenarios that display stylized facts of interest, such as cultural differentiation driven by many different mechansims including resource availability, migration, trade, and combat. The Sugarscape model was modified so as to reproduce the results of the Axelrod cultural model. Among the questions we address are: what does it mean for two models to be equivalent, how can different standards of equivalence be statistically evaluated, and how do subtle differences in model design affect the results? After attaining a “docking” of the two models, the richer set of mechanisms of the Sugarscape model is used to provide two experiments in sensitivity analysis for the cultural rule of Axelrod's model. Our generally positive experience in this enterprise has suggested that it could be beneficial if alignment and equivalence testing were more widely practiced among computational modelers.     

约束下线性混合模型参数估计的渐近解及其收敛性

在线性不等式约束下讨论了具有相同参数的两个线性混合模型的参数估计问题,给出了一种迭代算法,得到了这类模型中参数的最小二乘估计序列及其渐近解.在此基础上,利用多元多项式方程组解的个数定理和不动点定理,证明了此估计序列是依概率1收敛的.     

FK-映射的匹配定理及其对约束多目标对策的应用

利用 KKM 技巧,建立了FC-空间中转移紧开值FK-映射的Ky Fan匹配定理.作为应用,获得了FC-空间中的Ky Fan重合定理、约束多目标对策的加权 Nash-平衡和Pareto-平衡的存在定理.     

Constrained Markov control processes in Borel spaces: the discounted case

We consider constrained discounted-cost Markov control processes in Borel spaces, with unbounded costs. Conditions are given for the constrained problem to be solvable, and also equivalent to an equality-constrained (EC) linear program. In addition, it is shown that there is no duality gap between EC and its dual program EC^*, and that, under additional assumptions, also EC^* is solvable, so that in fact the strong duality condition holds. Finally, a Farkas-like theorem is included, which gives necessary and sufficient conditions for the primal program EC to be consistent.     

University objectives and socioeconomic results: A multicriteria measuring of alignment

Universities develop technology transfer mechanisms as the tools required to undertake missions committed to the socioeconomic environment. In this work a new proposal to measure the extent to which the goals or strategic objectives of a university are aligned with the results obtained through its technology transfer mechanisms with the local community is presented. This will enable to perform a diagnosis, by comparing the situation sought by the University Management team (expected case) with the actual one that derives from the application of the plans that implement the technology transfer mechanisms (real case). To achieve this, two different Multicriteria Decision Analysis techniques e.g. Analytic Network Process (ANP) and Analytic Hierarchy Process (AHP) will be used. Both the methodology and the MCDA techniques proposed need to be explained and clarified to the different experts who collaborate in the study, hence the facilitating process, key to the whole procedure, will be analysed in detail.The model proposed in this study is applied to analyse the case of the National University of Colombia – Bogotá Campus. Findings show that the following questions can be answered: (i) How much importance is granted by the University Management to the objectives of the University? (ii) To what extent are the objectives of the university fulfilled by the technology transfer mechanisms to the socioeconomic environment? (iii) Are the objectives of the university aligned with the results achieved through the technology transfer mechanisms?     

Neighborhood functions and hill-climbing strategies dedicated to the generalized ungapped local multiple alignment

Ungapped Local Multiple Alignment is a widely used procedure in bioinformatics. It roughly consists of locating in a given set of nucleotide (DNA) or amino acid (proteins) sequences, a number of non-overlapping fixed-size factors (also called occurrences), that are likely to have evolved from a common ancestor. In addition to the widely known statistical approaches, we define the problem from a pure combinatorial optimization point of view, by defining specific neighborhood functions and a hill-climbing strategy for each of four particular instances of this problem: (1) one occurrence per sequence, (2) at most one occurrence per sequence, (3) at least one occurrence per sequence, and (4) any number of occurrences per sequence. The method is implemented in a tool called Nomad (Neighborhood Optimization for Multiple Alignment Discovery) and a web interface is available at www.expasy.org/tools/nomad.html.     

A model of product line design and introduction sequence with reservation utility

Cannibalization is a major concern for a firm when designing a product line. In addition, external options from outside the firm’s product line may also play a significant role. In this paper, we investigate the impact of external options, represented by reservation utility, on product line design and introduction sequence. We find that: (a) heterogeneous reservation utility defines the relative attractiveness of segments and corresponding product line; (b) reservation utility makes it more favorable to introduce products sequentially rather than simultaneously; (c) aggregating segments is an effective way to mitigate cannibalization when it becomes too difficult to manage with different values of reservation utility across multiple segments; and (d) introducing products in a non-monotone order of quality can improve profit from simultaneous introduction when the value of reservation utility of a middle segment is particularly high.     

Averaged Subgradient Methods for Constrained Convex Optimization and Nash Equilibria Computation

We consider the problem of finding minima of convex functions under convex inequality constraints as well as the problem of finding Nash equilibria in n -person constant sum games. We prove that both problems can be solved by algorithms whose basic principles consist of representing the original problems as infinite systems of convex inequalities which, in turn, can be approached by outer projection techniques. Experiments showing how one of these algorithms behaves in test cases are presented and, in context, we describe a numerical method for computing subgradients of convex functions.     

Constrained Markov decision processes with total cost criteria: Occupation measures and primal LP

This paper is the third in a series on constrained Markov decision processes (CMDPs) with a countable state space and unbounded cost. In the previous papers we studied the expected average and the discounted cost. We analyze in this paper the total cost criterion. We study the properties of the set of occupation measures achieved by different classes of policies; we then focus on stationary policies and on mixed deterministic policies and present conditions under which optimal policies exist within these classes. We conclude by introducing an equivalent infinite Linear Program.     

A Four-filtrated may spectral sequence and its applications

In this paper, we introduce a four-filtrated version of the May spectral sequence (MSS), from which we study the general properties of the spectral sequence and give a collapse theorem. We also give an efficient method to detect generators of May E ₁-term E ₁ ^s,t,b,* for a given (s, t, b, *). As an application, we give a method to prove the non-triviality of some compositions of the known homotopy elements in the classical Adams spectral sequence (ASS). This research is partially supported by the National Natural Science Foundation of China (Nos. 10501045, 10771105) and the Fund of the Personnel Division of Nankai University