TY - GEN

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

AU - Chao, Kun Mao

AU - Chu, An Chiang

AU - Jansson, Jesper Andreas

AU - Lemence, Richard S.

AU - Mancheron, Alban

PY - 2012/5/18

Y1 - 2012/5/18

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84861005661&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-29952-0_21

DO - 10.1007/978-3-642-29952-0_21

M3 - Conference article published in proceeding or book

SN - 9783642299513

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 177

EP - 188

BT - Theory and Applications of Models of Computation - 9th Annual Conference, TAMC 2012, Proceedings

T2 - 9th Annual Conference on Theory and Applications of Models of Computation, TAMC 2012

Y2 - 16 May 2012 through 21 May 2012

ER -