Search

Genomic sequences display characteristic features at various scales ranging from oligonucleotide frequencies to large organizational units such as genes. The generation of such a sequence, defined as a string over the alphabet SigmaDNA={A C, T, G}, can be approximated by a formal machine, a Markov chain having strings as states, whose parameters lend unique characteristics to the sequence. We present a formal mathematical framework that analyzes this approximation in terms of transition probabilities of words at various scales. Within this framework, we present an algorithm that estimates the order of the Markov chain of order omega hypothesized to have generated a sequence S at hand. Consider the probability of transition from string alpha to string gamma both of length omega, computed using both order w and order omega-1 Markov chains. The expected difference of the two probabilities thus obtained, is zero, and demonstrates a sharp positive transition for values of omega between omega and omega+1. Both mathematical and experimental results are obtained that explain the general behavior of the algorithm.

An important problem in high-throughput protein crystallography is constructing a protein model from an electron-density map. Previous work by some of this paper's authors [1] describes an automated approach to this otherwise time-consuming process. An important step in the previous method requires searching the density map for many small template protein-fragments. This previous approach uses Fourier convolution to quickly match some rotation of the template to the entire density map. This paper proposes an alternate approach that makes use of the spherical-harmonic decomposition of the template and of some region in the density map. This new framework allows us to mask specific regions of the map, enabling a first-pass filter to eliminate a majority of the density map without requiring an expensive rotational search. We show our new template matching method improves accuracy and reduces running time, compared to our previous approach. Protein models constructed using this matching also show significant accuracy improvement.