剖面隐马氏模型训练算法的改进

利用剖面隐马氏模型获得多序列联配，一般需要经过初始化、训练、联配三个过程．然而，目前广泛采用的Baum—welch训练算法假设各条可观察序列互相独立，这与实际情况有所不符．本文对剖面隐马氏模型，给出可观察序列在互相不独立情况下的改进Baum—wlelch算法，在可观察序列两种特殊情况下（互相独立和一致依赖），得到了改进算法的具体表达式，讨论了一般情况下权重的选取方法．最后通过一个具体的蛋白质家族的多序列联配来说明改进算法的效果．     

Improved Approximation Algorithms for Tree Alignment

Multiple sequence alignment is a task at the heart of much of current computational biology[4]. Several different objective functions have been proposed to formalize the task of multiple sequence alignment, but efficient algorithms are lacking in each case. Thus multiple sequence alignment is one of the most critical, essentially unsolved problems in computational biology. In this paper we consider one of the more compelling objective functions for multiple sequence alignment, formalized as thetree alignment problem. Previously in[13], a ratio-two approximation method was developed for tree alignment, which ran incubictime (as a function of the number of fixed length strings to be aligned), along with a polynomial time approximation scheme (PTAS) for the problem. However, the PTAS in[13]had a running time which made it impractical to reduce the performance ratio much below two for small size biological sequences (100 characters long). In this paper we first develop a ratio-two approximation algorithm which runs inquadratictime, and then use it to develop a PTAS which has a better performance ratio and a vastly improved worst case running time compared to the scheme in[13]for the case where the given tree is a regular deg-ary tree. With the new approximation scheme, it is now practical to guarantee a ratio of 1.583 for strings of lengths 200 characters or less.     

On the counting function of the lattice profile of periodic sequences

The lattice profile analyzes the intrinsic structure of pseudorandom number sequences with applications in Monte Carlo methods and cryptology. In this paper, using the discrete Fourier transform for periodic sequences and the relation between the lattice profile and the linear complexity, we give general formulas for the expected value, variance, and counting function of the lattice profile of periodic sequences with fixed period. Moreover, we determine in a more explicit form the expected value, variance, and counting function of the lattice profile of periodic sequences for special values of the period.     

Likelihood-based Inference for the Ratios of Regression Coefficients in Linear Models

We consider the standard linear multiple regression model in which the parameter of interest is the ratio of two regression coefficients. Our setup includes a broad range of applications. We show that the 1− α confidence interval for the interest parameter based on the profile, conditional profile, modified profile or adjusted profile likelihood can potentially become the entire real line, while appropriately chosen integrated likelihoods do not suffer from this drawback. We further explore the asymptotic length of confidence intervals in order to compare integrated likelihood-based proposals. The analysis is facilitated by an orthogonal parameterization.     

DCA based algorithms for multiple sequence alignment (MSA)

In the last years many techniques in bioinformatics have been developed for the central and complex problem of optimally aligning biological sequences. In this paper we propose a new optimization approach based on DC (Difference of Convex functions) programming and DC Algorithm (DCA) for the multiple sequence alignment in its equivalent binary linear program, called “Maximum Weight Trace” problem. This problem is beforehand recast as a polyhedral DC program with the help of exact penalty techniques in DC programming. Our customized DCA, requiring solution of a few linear programs, is original because it converges after finitely many iterations to a binary solution while it works in a continuous domain. To scale-up large-scale (MSA), a constraint generation technique is introduced in DCA. Preliminary computational experiments on benchmark data show the efficiency of the proposed algorithm DCAMSA, which generally outperforms some standard algorithms.     

The theory and computation of evolutionary distances: Pattern recognition

A method of finding pattern similarities between two sequences is given. Two portions, one from each sequence, are similar if they are close in the metric space of evolutionary distances. The method allows a complete list to be made of all pairs of intervals, one from each of two given sequences, such that each pair displays a maximum local degree of similarity, and, if the lengths of the given sequences are m and n, then the procedure takes on the order of mn computational steps. This result lends itself to finding similarities by computer between pairs of biological sequences, such as proteins and nucleic acids.     

Bayesian Monte Carlo estimation for profile hidden Markov models

Hidden Markov models are used as tools for pattern recognition in a number of areas, ranging from speech processing to biological sequence analysis. Profile hidden Markov models represent a class of so-called “left–right” models that have an architecture that is specifically relevant to classification of proteins into structural families based on their amino acid sequences. Standard learning methods for such models employ a variety of heuristics applied to the expectation-maximization implementation of the maximum likelihood estimation procedure in order to find the global maximum of the likelihood function. Here, we compare maximum likelihood estimation to fully Bayesian estimation of parameters for profile hidden Markov models with a small number of parameters. We find that, relative to maximum likelihood methods, Bayesian methods assign higher scores to data sequences that are distantly related to the pattern consensus, show better performance in classifying these sequences correctly, and continue to perform robustly with regard to misspecification of the number of model parameters. Though our study is limited in scope, we expect our results to remain relevant for models with a large number of parameters and other types of left–right hidden Markov models.     

A population global optimization algorithm to solve the image alignment problem in electron crystallography

Knowledge of the structure of biological specimens is critical to understanding their function. Electron crystallography is an electron microscopy (EM) approach that derives the 3D structure of specimens at high-resolution, even at atomic detail. Prior to the tomographic reconstruction, the images taken from the microscope have to be properly aligned. Traditional alignment methods in electron crystallography are based on a phase residual function to be minimized by inefficient exhaustive search procedures. This work addresses this minimization problem from an evolutionary perspective. Universal Evolutionary Global Optimizer (UEGO), an evolutionary multimodal optimization algorithm, has been applied and evaluated for the task of image alignment in this field. UEGO has turned out to be a promising technique alternative to the standard methodology. The alignments found out by UEGO show high levels of accuracy, while reducing the number of function evaluations by a significant factor with respect to the standard method.     

隐马尔可夫模型在生物信息学中的应用

隐马尔可夫模型 ( HMM)是一个能够通过可观测的数据很好地捕捉真实空间统计性质的随机模型 ,该模型已成功地运用于语音识别 ,目前 HMM已开始应用于生物信息学 ( bioinformatics) ,已在生物序列分析中得到了广泛的应用 .本文首先介绍了 HMM的基本结构 ,然后着重讨论了 HMM在 DNA序列的多重比对 ,基因发现等生物序列分析中的应用     

Some biological sequence metrics

Some new metrics are introduced to measure the distance between biological sequences, such as amino acid sequences or nucleotide sequences. These metrics generalize a metric of Sellers, who considered only single deletions, mutations, and insertions. The present metrics allow, for example, multiple deletions and insertions and single mutations. They also allow computation of the distance among more than two sequences. Algorithms for computing the values of the metrics are given which also compute best alignments. The connection with the information theory approach of Reichert, Cohen, and Wong is discussed.     

Introduction to the Peptide Binding Problem of Computational Immunology: New Results

We attempt to establish geometrical methods for amino acid sequences. To measure the similarities of these sequences, a kernel on strings is defined using only the sequence structure and a good amino acid substitution matrix (e.g. BLOSUM62). The kernel is used in learning machines to predict binding affinities of peptides to human leukocyte antigen DR (HLA-DR) molecules. On both fixed allele (Nielsen and Lund in BMC Bioinform. 10:296, 2009) and pan-allele (Nielsen et al. in Immunome Res. 6(1):9, 2010) benchmark databases, our algorithm achieves the state-of-the-art performance. The kernel is also used to define a distance on an HLA-DR allele set based on which a clustering analysis precisely recovers the serotype classifications assigned by WHO (Holdsworth et al. in Tissue Antigens 73(2):95–170, 2009; Marsh et al. in Tissue Antigens 75(4):291–455, 2010). These results suggest that our kernel relates well the sequence structure of both peptides and HLA-DR molecules to their biological functions, and that it offers a simple, powerful and promising methodology to immunology and amino acid sequence studies.     

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.     

Constrained sequence alignment: A general model and the hardness results

Imposing constraints is a way to incorporate information into the sequence alignment procedure. In this paper, a general model for constrained alignment is proposed so that analyses admitted are more flexible and that different pattern definitions can be treated in a simple unified way. We give a polynomial time algorithm for pairwise constrained alignment for the generalized formulation, and prove the inapproximability of the problem when the number of sequences can be arbitrary. In addition, previous works deal only with the case that the patterns in the constraint have to occur in the output alignment in the same order as that specified by the input. It is of both theoretical and practical interest to investigate the case when the order is no longer limited. We show that the problem is not approximable even when the number of sequences is two. We also give the NPO-completeness results for the problems with bounds imposed on the objective function value.     

Lossless filter for multiple repetitions with Hamming distance

Similarity search in texts, notably in biological sequences, has received substantial attention in the last few years. Numerous filtration and indexing techniques have been created in order to speed up the solution of the problem. However, previous filters were made for speeding up pattern matching, or for finding repetitions between two strings or occurring twice in the same string. In this paper, we present an algorithm called Nimbus for filtering strings prior to finding repetitions occurring twice or more in a string, or in two or more strings. Nimbus uses gapped seeds that are indexed with a new data structure, called a bi-factor array, that is also presented in this paper. Experimental results show that the filter can be very efficient: preprocessing with Nimbus a data set where one wants to find functional elements using a multiple local alignment tool such as Glam, the overall execution time can be reduced from 7.5 hours to 2 minutes.     

Local linear regression for data with AR errors

In many statistical applications, data are collected over time, and they are likely correlated. In this paper, we investigate how to incorporate the correlation information into the local linear regression. Under the assumption that the error process is an auto-regressive process, a new estimation procedure is proposed for the nonparametric regression by using local linear regression method and the profile least squares techniques. We further propose the SCAD penalized profile least squares method to determine the order of auto-regressive process. Extensive Monte Carlo simulation studies are conducted to examine the finite sample performance of the proposed procedure, and to compare the performance of the proposed procedures with the existing one. From our empirical studies, the newly proposed procedures can dramatically improve the accuracy of naive local linear regression with working-independent error structure. We illustrate the proposed methodology by an analysis of real data set.     

Global alignment of molecular sequences via ancestral state reconstruction

We consider the trace reconstruction problem on a tree (TRPT): a binary sequence is broadcast through a tree channel where we allow substitutions, deletions, and insertions; we seek to reconstruct the original sequence from the sequences received at the leaves. The TRPT is motivated by the multiple sequence alignment problem in computational biology. We give a simple recursive procedure giving strong reconstruction guarantees at low mutation rates. To our knowledge, this is the first rigorous trace reconstruction result on a tree in the presence of indels.     

Locating a metro line in a historical city centre: application to Sevilla

When constructing a metro alignment under a historical city centre, it is important to generate a cost-effective path while maintaining a minimum distance between the alignment and historical buildings. This paper describes a simple methodology for generating a set of good alternative solutions. It is based on the use of Voronoi diagrams. The method was applied to data from the city of Sevilla.     

A Bayesian record linkage model incorporating relational data

In this article, we introduce a novel Bayesian approach for linking multiple social networks in order to discover the same real world person having different accounts across networks. In particular, we develop a latent model that allows us to jointly characterize the network and linkage structures relying on both relational and profile data. In contrast to other existing approaches in the machine learning literature, our Bayesian implementation naturally provides uncertainty quantification via posterior probabilities for the linkage structure itself or any function of it. Our findings clearly suggest that our methodology can produce accurate point estimates of the linkage structure even in the absence of profile information, and also, in an identity resolution setting, our results confirm that including relational data into the matching process improves the linkage accuracy. We illustrate our methodology using real data from popular social networks such as Twitter , Facebook , and YouTube .     

A general mathematical model for two-parameter generating machining of involute cylindrical gears

Instead of the common analytical model for involute gears machining, a general mathematical model for two-parameter generating machining is developed in this study with adopting discrete enveloping to increase its robustness and generality for machined profile calculation and instant contact analysis. The geometric parameters and motion relationships are integrated according to the cross-axis gear meshing at first, and the enveloping theory for two-parameter generating process is analyzed briefly with involving middle gear rack. By transforming the multiple cutting edges relative to the gear blank according to the generating motions, a numerical algorithm is proposed to distinguish the external enveloping profile on the shaft section, then the derivation of instant contact points via the implied time sequences of profile points is introduced. Finally, the coordinate transformations for the spatial trajectory of instant contact points identifying and the engaged cutting edge segments distinguishing are investigated. At last, a non- involute profile skiving is performed to verify the generality and the robustness of proposed method, and several typically generating machining operations for cylindrical involute gear are simulated numerically to proof the accuracy of the proposed model by finding the deviations from the standard involute curves and the geometries of the instant contact points.     

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.