An efficient polynomial space and polynomial delay algorithm for enumeration of maximal motifs in a sequence

In this paper, we consider the problem of enumerating all maximal motifs in an input string for the class of repeated motifs with wild cards. A maximal motif is such a representative motif that is not properly contained in any larger motifs with the same location lists. Although the enumeration problem for maximal motifs with wild cards has been studied in Parida et al. (2001), Pisanti et al. (2003) and Pelfrêne et al. (2003), its output-polynomial time computability has been still open. The main result of this paper is a polynomial space polynomial delay algorithm for the maximal motif enumeration problem for the repeated motifs with wild cards. This algorithm enumerates all maximal motifs in an input string of length n in O(n ³) time per motif with O(n) space, in particular O(n ³) delay. The key of the algorithm is depth-first search on a tree-shaped search route over all maximal motifs based on a technique called prefix-preserving closure extension. We also show an exponential lower bound and a succinctness result on the number of maximal motifs, which indicate the limit of a straightforward approach. The results of the computational experiments show that our algorithm can be applicable to huge string data such as genome data in practice, and does not take large additional computational cost compared to usual frequent motif mining algorithms. This work is done during the Hiroki Arimura’s visit in LIRIS, University Claude-Bernard Lyon 1, France.     

Construdtion of shrinkage estimators for the regression coefficient matrix in the gmanova model

This paper extensively investigates the theory of estimating the regression coefficient matrix in the normal GM.4KOVA model. We explicitly construct estimators which improve upon the maximum likelihood estimator under an invariant scalar loss function. These include the double shrinkage estimatois and those shrinking the maximum likelihood estimators directly. The underlying method is the decomposition of the problem into the conditional subproblems due to Kariya, Konno, and Strawderman(l996) and application of integration-by-parts technique to derive an unbiased estimate of the risk for certain class of invariant estimators.     

Tests for multinormality with applications to time series

Making use of a characterization of multivariate normality by Hermitian polynomials, we propose a multivariate normality test. The approach is then applied to time series analysis by constructing a test for Gaussianity of a stationary univariate series. Simulation study shows that the proposed test has reasonable power and outperforms other tests available in the literature when the innovation series of the time series is symmetric, but non-Gaussian.