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
Communication Dans Un Congrès Année : 2012

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

Résumé

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
Origine Fichiers éditeurs autorisés sur une archive ouverte
Loading...

Dates et versions

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

Identifiants

Citer

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⟩
171 Consultations
456 Téléchargements

Altmetric

Partager

More