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 -