Asymptotic limits of a new type of maximization recurrence with an application to bioinformatics

Kun Mao Chao, An Chiang Chu, Jesper Andreas Jansson, Richard S. Lemence, Alban Mancheron

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

Abstract

We study the asymptotic behavior of a new type of maximization recurrence, defined as follows. Let k be a positive integer and pk(x) a polynomial of degree k satisfying pk(0) = 0. Define A0= 0 and for n ≥ 1, let An= max0≤i<n{Ai+nkpk(i/n)}. We prove that limn→∞An/nn= sup{pk(x)/1-xk: 0≤x<1}. We also consider two closely related maximization recurrences Snand S′n, defined as S0= S′0= 0, and for n ≥ 1, Sn= max0≤i<n{Si+ i(n-i)(n-i-1)/2} and S′n= max0≤i<n{S′i+ (3n-i) + 2i(2n-i) + (n-i)(2i)}. We prove that limn→∞S′n/3(3n) = 2(√3-1)/3 ≈ 0.488033..., resolving an open problem from Bioinformatics about rooted triplets consistency in phylogenetic networks.
Original languageEnglish
Title of host publicationTheory and Applications of Models of Computation - 9th Annual Conference, TAMC 2012, Proceedings
Pages177-188
Number of pages12
DOIs
Publication statusPublished - 18 May 2012
Externally publishedYes
Event9th Annual Conference on Theory and Applications of Models of Computation, TAMC 2012 - Beijing, China
Duration: 16 May 201221 May 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7287 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference9th Annual Conference on Theory and Applications of Models of Computation, TAMC 2012
Country/TerritoryChina
CityBeijing
Period16/05/1221/05/12

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this