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

doi:10.1007/978-3-642-29952-0_21

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 proceeding › Conference article published in proceeding or book › Academic research › peer-review

1 Citation (Scopus)

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 language	English
Title of host publication	Theory and Applications of Models of Computation - 9th Annual Conference, TAMC 2012, Proceedings
Pages	177-188
Number of pages	12
DOIs	https://doi.org/10.1007/978-3-642-29952-0_21
Publication status	Published - 18 May 2012
Externally published	Yes
Event	9th Annual Conference on Theory and Applications of Models of Computation, TAMC 2012 - Beijing, China Duration: 16 May 2012 → 21 May 2012

Publication series

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

Conference

Conference	9th Annual Conference on Theory and Applications of Models of Computation, TAMC 2012
Country/Territory	China
City	Beijing
Period	16/05/12 → 21/05/12

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

More information

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

Cite this

Chao, K. M., Chu, A. C., Jansson, J. A., Lemence, R. S., & Mancheron, A. (2012). Asymptotic limits of a new type of maximization recurrence with an application to bioinformatics. In Theory and Applications of Models of Computation - 9th Annual Conference, TAMC 2012, Proceedings (pp. 177-188). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7287 LNCS). https://doi.org/10.1007/978-3-642-29952-0_21

Chao, Kun Mao ; Chu, An Chiang ; Jansson, Jesper Andreas et al. / Asymptotic limits of a new type of maximization recurrence with an application to bioinformatics. Theory and Applications of Models of Computation - 9th Annual Conference, TAMC 2012, Proceedings. 2012. pp. 177-188 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{2cb2cbff582747c2837e8f1cb95d771c,

title = "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 pk(x) a polynomial of degree k satisfying pk(0) = 0. Define A0= 0 and for n ≥ 1, let An= max0≤i",

author = "Chao, \{Kun Mao\} and Chu, \{An Chiang\} and Jansson, \{Jesper Andreas\} and Lemence, \{Richard S.\} and Alban Mancheron",

year = "2012",

month = may,

day = "18",

doi = "10.1007/978-3-642-29952-0\_21",

language = "English",

isbn = "9783642299513",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "177--188",

booktitle = "Theory and Applications of Models of Computation - 9th Annual Conference, TAMC 2012, Proceedings",

note = "9th Annual Conference on Theory and Applications of Models of Computation, TAMC 2012 ; Conference date: 16-05-2012 Through 21-05-2012",

}

Chao, KM, Chu, AC, Jansson, JA, Lemence, RS & Mancheron, A 2012, Asymptotic limits of a new type of maximization recurrence with an application to bioinformatics. in Theory and Applications of Models of Computation - 9th Annual Conference, TAMC 2012, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7287 LNCS, pp. 177-188, 9th Annual Conference on Theory and Applications of Models of Computation, TAMC 2012, Beijing, China, 16/05/12. https://doi.org/10.1007/978-3-642-29952-0_21

Asymptotic limits of a new type of maximization recurrence with an application to bioinformatics. / Chao, Kun Mao; Chu, An Chiang; Jansson, Jesper Andreas et al.
Theory and Applications of Models of Computation - 9th Annual Conference, TAMC 2012, Proceedings. 2012. p. 177-188 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7287 LNCS).

Research output: Chapter in book / Conference proceeding › Conference article published in proceeding or book › Academic research › peer-review

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

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

UR - https://www.scopus.com/pages/publications/84861005661

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 -

Chao KM, Chu AC, Jansson JA, Lemence RS, Mancheron A. Asymptotic limits of a new type of maximization recurrence with an application to bioinformatics. In Theory and Applications of Models of Computation - 9th Annual Conference, TAMC 2012, Proceedings. 2012. p. 177-188. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-29952-0_21

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

Abstract

Publication series

Conference

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this