Asymptotic Limits of a New Type of Maximization Recurrence with an Application to Bioinformatics - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2012

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.
Fichier principal
Vignette du fichier
CHAO2012.pdf (251.88 Ko) Télécharger le fichier
Origin Publisher files allowed on an open archive
Loading...

Dates and versions

lirmm-00717670 , version 1 (13-07-2012)

Identifiers

Cite

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⟩
166 View
447 Download

Altmetric

Share

More