Skip to Main content Skip to Navigation
Conference papers

Asymptotic Limits of a New Type of Maximization Recurrence with an Application to Bioinformatics

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 \geq 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 \geq 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.
Complete list of metadatas

Cited literature [16 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00717670
Contributor : Alban Mancheron <>
Submitted on : Friday, July 13, 2012 - 12:55:09 PM
Last modification on : Thursday, February 7, 2019 - 5:55:15 PM
Long-term archiving on: : Sunday, October 14, 2012 - 2:45:47 AM

File

CHAO2012.pdf
Publisher files allowed on an open archive

Identifiers

Collections

Citation

Kun-Mao Chao, An-Chiang Chu, Jesper Jansson, Richard S. Lemence, Alban Mancheron. Asymptotic Limits of a New Type of Maximization Recurrence with an Application to Bioinformatics. TAMC'12: 9th Annual Conference on Theory and Applications of Models of Computation, May 2012, Beijing, China. pp.622, ⟨10.1007/978-3-642-29952-0⟩. ⟨lirmm-00717670⟩

Share

Metrics

Record views

272

Files downloads

578