排序方式: 共有6条查询结果,搜索用时 0 毫秒
1
1.
Genome rearrangement algorithms are powerful tools to analyze gene orders in molecular evolution. Analysis of genomes evolving by reversals and transpositions leads to a combinatorial problem of sorting by reversals and transpositions, the problem of finding a shortest sequence of reversals and transpositions that sorts one genome into the other. In this paper we present a 2k-approximation algorithm for sorting by reversals and transpositions for unsigned permutations where k is the approximation ratio of the algorithm used for cycle decomposition. For the best known value of k our approximation ratio becomes 2.8386+δ for any δ>0. We also derive a lower bound on reversal and transposition distance of an unsigned permutation. 相似文献
2.
Paul Fearnhead Robert Maidstone Adam Letchford 《Journal of computational and graphical statistics》2019,28(2):265-275
While there are many approaches to detecting changes in mean for a univariate time series, the problem of detecting multiple changes in slope has comparatively been ignored. Part of the reason for this is that detecting changes in slope is much more challenging: simple binary segmentation procedures do not work for this problem, while existing dynamic programming methods that work for the change in mean problem cannot be used for detecting changes in slope. We present a novel dynamic programming approach, CPOP, for finding the “best” continuous piecewise linear fit to data under a criterion that measures fit to data using the residual sum of squares, but penalizes complexity based on an L0 penalty on changes in slope. We prove that detecting changes in this manner can lead to consistent estimation of the number of changepoints, and show empirically that using an L0 penalty is more reliable at estimating changepoint locations than using an L1 penalty. Empirically CPOP has good computational properties, and can analyze a time series with 10,000 observations and 100 changes in a few minutes. Our method is used to analyze data on the motion of bacteria, and provides better and more parsimonious fits than two competing approaches. Supplementary material for this article is available online. 相似文献
3.
Phillip E.C. Compeau 《Discrete Applied Mathematics》2011,159(15):1641-1645
We consider four families of pancake graphs, which are Cayley graphs, whose vertex sets are either the symmetric group on n objects or the hyperoctahedral group on n objects and whose generating sets are either all reversals or all reversals inverting the first k elements (called prefix reversals). We find that the girth of each family of pancake graphs remains constant after some small threshold value of n. 相似文献
4.
This paper develops a real time algorithm which identifies times of emotional discontinuity as reflected in social media. The paper formulates the optimization problem to solve, develops an algorithm to solve it using dynamic programming, and illustrates the new method by analyzing mood shifts reflected in 380,000 Twitter messages related to one of the world’s most popular soccer teams, Manchester United, during their 2011–12 season. 相似文献
5.
David Bryant 《Journal of Discrete Algorithms》2004,2(2):229
Breakpoint phylogenies methods have been shown to be an effective tool for extracting phylogenetic information from gene order data. Currently, the only practical breakpoint phylogeny algorithms for the analysis of large genomes with varied gene content are heuristics with no optimality guarantee. Here we begin to address this lack by deriving lower bounds for the breakpoint median problem and for the more complicated breakpoint phylogeny problem. In both cases we employ Lagrange multipliers and sub-gradient optimization to tighten the bounds. The bounds have been implemented and are available as part of the
package (http://www.math.mcgill.ca/bryant/gotree). 相似文献
6.
A changepoint in a time series is a time of change in the marginal distribution, autocovariance, or any other distributional structure of the series. Examples include mean level shifts and volatility (variance) changes. Climate data, for example, is replete with mean shift changepoints, occurring whenever a recording instrument is changed or the observing station is moved. Here, we consider the problem of incorporating known changepoint times into a regression model framework. Specifically, we establish consistency and asymptotic normality of ordinary least squares regression estimators that account for an arbitrary number of mean shifts in the record. In a sense, this provides an alternative to the customary infill asymptotics for regression models that assume an asymptotic infinity of data observations between all changepoint times. 相似文献
1