Abstract
We study the asymptotic behavior of a new type of maximization recurrence, defined as follows. Let k be a positive integer and p k (x) a polynomial of degree k satisfying p k (0) = 0. Define A 0 = 0 and for n ≥ 1, let \(A_{n} = \max\nolimits_{0 \leq i < n} \{ A_{i} + n^{k} \, p_{k}(\frac{i}{n}) \}\). We prove that \(\lim_{n \rightarrow \infty} \frac{A_{n}}{n^k} \,=\, \sup \{ \frac{p_k(x)}{1-x^k}: 0 \leq x <1\}\). We also consider two closely related maximization recurrences S n and S′ n , defined as S 0 = S′0 = 0, and for n ≥ 1, \(S_{n} = \max\nolimits_{0 \leq i < n} \{ S_{i} + \frac{i(n-i)(n-i-1)}{2} \}\) and \(S'_{n} = \max\nolimits_{0 \leq i < n} \{ S'_{i} + {n-i \choose 3} + 2i { n-i \choose 2} + (n-i){ i \choose 2} \}\). We prove that \(\lim\nolimits_{n \rightarrow \infty} \frac{S_{n}}{n^3} = \frac{2\sqrt{3}-3}{6} \approx 0.077350...\) and \(\lim\nolimits_{n \rightarrow \infty} \frac{S'_{n}}{3{n \choose 3}} = \frac{2(\sqrt{3}-1)}{3} \approx 0.488033...\), resolving an open problem from Bioinformatics about rooted triplets consistency in phylogenetic networks.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bininda-Emonds, O.R.P.: The evolution of supertrees. Trends in Ecology and Evolution 19(6), 315–322 (2004)
Byrka, J., Gawrychowski, P., Huber, K.T., Kelk, S.: Worst-case optimal approximation algorithms for maximizing triplet consistency within phylogenetic networks. Journal of Discrete Algorithms 8(1), 65–75 (2010)
Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to Algorithms, 3rd edn. The MIT Press, Massachusetts (2009)
Felsenstein, J.: Inferring Phylogenies. Sinauer Associates, Inc., Sunderland (2004)
Fredman, M.L., Knuth, D.E.: Recurrence relations based on minimization. Journal of Mathematical Analysis and Applications 48(2), 534–559 (1974)
Gąsieniec, L., Jansson, J., Lingas, A., Östlin, A.: On the complexity of constructing evolutionary trees. Journal of Combinatorial Optimization 3(2-3), 183–197 (1999)
Gusfield, D., Eddhu, S., Langley, C.: Efficient reconstruction of phylogenetic networks with constrained recombination. In: Proceedings of the Computational Systems Bioinformatics Conference (CSB2 2003), pp. 363–374 (2003)
Henzinger, M.R., King, V., Warnow, T.: Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology. Algorithmica 24(1), 1–13 (1999)
Hwang, H.-K., Tsai, T.-H.: An asymptotic theory for recurrence relations based on minimization and maximization. Theoretical Computer Science 290(3), 1475–1501 (2003)
Huson, D.H., Rupp, R., Scornavacca, C.: Phylogenetic Networks: Concepts, Algorithms and Applications. Cambridge University Press (2010)
Jansson, J., Nguyen, N., Sung, W.: Algorithms for combining rooted triplets into a galled phylogenetic network. SIAM Journal on Computing 35(5), 1098–1121 (2006)
Kapoor, S., Reingold, E.M.: Recurrence relations based on minimization and maximization. Journal of Mathematical Analysis and Applications 109(2), 591–604 (1985)
Li, Z., Reingold, E.M.: Solution of a divide-and-conquer maximin recurrence. SIAM Journal on Computing 18(6), 1188–1200 (1989)
Morrison, D.: Introduction to Phylogenetic Networks. RJR Productions (2011)
Saha, A., Wagh, M.D.: Minmax recurrences in analysis of algorithms. In: Proceedings of Southeastcon 1993. IEEE (1993)
Wang, L., Ma, B., Li, M.: Fixed topology alignment with recombination. Discrete Applied Mathematics 104(1-3), 281–300 (2000)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chao, KM., Chu, AC., Jansson, J., Lemence, R.S., Mancheron, A. (2012). Asymptotic Limits of a New Type of Maximization Recurrence with an Application to Bioinformatics. In: Agrawal, M., Cooper, S.B., Li, A. (eds) Theory and Applications of Models of Computation. TAMC 2012. Lecture Notes in Computer Science, vol 7287. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-29952-0_21
Download citation
DOI: https://doi.org/10.1007/978-3-642-29952-0_21
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-29951-3
Online ISBN: 978-3-642-29952-0
eBook Packages: Computer ScienceComputer Science (R0)