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.
Type de document :
Communication dans un congrès
Manindra Agrawal and S. Barry Cooper and Angsheng Li. TAMC'12: 9th Annual Conference on Theory and Applications of Models of Computation, May 2012, Beijing, China. Springer, 7287, pp.622, 2012, Lecture Notes in Computer Science. 〈10.1007/978-3-642-29952-0〉
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00717670
Contributeur : Alban Mancheron <>
Soumis le : vendredi 13 juillet 2012 - 12:55:09
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13
Document(s) archivé(s) le : dimanche 14 octobre 2012 - 02:45:47

Fichier

CHAO2012.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

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. Manindra Agrawal and S. Barry Cooper and Angsheng Li. TAMC'12: 9th Annual Conference on Theory and Applications of Models of Computation, May 2012, Beijing, China. Springer, 7287, pp.622, 2012, Lecture Notes in Computer Science. 〈10.1007/978-3-642-29952-0〉. 〈lirmm-00717670〉

Partager

Métriques

Consultations de la notice

127

Téléchargements de fichiers

127