Statistical Data Compression
- PDF / 192,919 Bytes
- 1 Pages / 547.087 x 737.008 pts Page_size
- 13 Downloads / 209 Views
S 9.
10.
11. 12. 13.
14.
15.
Statistical Data Compression
tomata, Languages and Programming. LNCS, pp. 776–787. Springer (2002) Roughgarden, T.: Designing networks for selfish users is hard. In: 42nd IEEE Annual Symposium of Foundations of Computer Science, pp. 472–481 (2001) Roughgarden, T.: Stackelberg scheduling strategies. In: 33rd ACM Annual Symposium on Theory of Computing, pp. 104– 113 (2001) Roughgarden, T.: Selfish Routing. Dissertation, Cornell University, USA, May 2002, http://theory.stanford.edu/~tim/ Roughgarden, T.: Selfish Routing and the Price of Anarchy. The MIT Press, Cambridge (2005) Roughgarden, T., Tardos, E.: How bad is selfish routing? In: 41st IEEE Annual Symposium of Foundations of Computer Science, pp. 93–102. J. ACM 49(2), pp 236–259, 2002, ACM, New York (2000) Swamy, C.: The effectiveness of stackelberg strategies and tolls for network congestion games. In: ACM-SIAM Symposium on Discrete Algorithms, Philadelphia, PA, USA (2007) von Stackelberg, H.: Marktform und Gleichgewicht. Springer, Vienna (1934)
Statistical Data Compression Arithmetic Coding for Data Compression
Statistical Multiple Alignment 2003; Hein, Jensen, Pedersen ISTVÁN MIKLÓS Department of Plant Taxonomy and Ecology, Eötvös Lóránd University, Budapest, Hungary Keywords and Synonyms Evolutionary hidden Markov models Problem Definition The three main types of mutations modifying biological sequences are insertions, deletions and substitutions. The simplest model involving these three types of mutations is the so-called Thorne–Kishino–Felsenstein model [13]. In this model, the characters of a sequence evolve independently. Each character in the sequence can be substituted with another character according to a prescribed reversible time-continuous Markov model on the possible characters. Insertion-deletions are modeled as a birth-death process, characters evolve independently and identically, with insertion and deletion rates and . The multiple statistical alignment problem is to calculate the likelihood of a set of sequences, namely, what is the probability of observing a set of sequences, given
all the necessary parameters that describe the evolution of sequences. Hein, Jensen and Pedersen were the first who gave an algorithm to calculate this probability [4]. Their algorithm has O(5n L n ) running time, where n is the number of sequences, and L is the geometric mean of the sequences. The running time has been improved to O(2n L n ) by Lunter et al. [10]. Notations Insertions and Deletions In the Thorne–Kishino– Felsenstein model (TKF91 model) [13], both the birth and the death processes are Poisson processes with parameters and , respectively. Since each character evolves independently, the probability of an insertion-deletion pattern given by an alignment can be calculated as the product of the probabilities of patterns. Each pattern starts with an ancestral character, except the first that starts with the beginning of the alignment, end ends before the next ancestral character, except the last that ends at t
Data Loading...
