A280430 Longest word T from 2 equal length strings S using no breakpoint reuse.

2, 4, 7, 14, 19, 34, 63, 76, 137, 248, 282, 502, 891, 980, 1718, 3000, 3233, 5594, 9646, 10256, 17565, 30000, 31597, 53690, 91033, 95214, 160803, 271108, 282054, 474060, 795677, 824334, 1380142, 2308114, 2383139, 3977364, 6631898, 6828316, 11366227

Offset: 0

Author

Nicole Anderson, Jan 02 2017

Keywords

• nonn

Comments

We start with two strings, of length n, that are the identity permutation of alphabet letters. The space between two adjacent letters is called a breakpoint. We then apply duplications, which take a substring from one string and insert it into the center of the other string. Each duplication uses three breakpoints; two for the substring and one for its destination. Each breakpoint can only be used once. This alternating duplications pattern produces a word T. The formula for the longest possible T uses the length of each string (n).

Examples

			In this case, S is 2 strings with length 5. There are 8 breakpoints so 2 duplications can be made. The longest possible T has length 19 which can be obtained using the process below.
ABCDE FGHIJ
A|BCD|E  FG|HIJ becomes ABCDE FGBCDHIJ after inserting BCD between G and H.
AB|CDE  F|GBCDHI|J becomes ABGBCDHICDE FGBCDHIJ after inserting GBCDHI between B and C.
		

References

• N. I. Anderson, M. J. Paukner, M. R. Riehl, and A. M. Steinman, String Duplication Histories with No-Breakpoint-Reuse, preprint.

Links

• Brona Brejová, Gad M. Landau, Tomáš Vinar, Fast computation of a string duplication history under no-breakpoint-reuse, Philos T Roy Soc A 372:20130133.
• Jean-Philippe Doyon, Vincent Ranwez, Vincent Daubin, Vincent Berry, Models, algorithms and programs for phylogeny reconciliation, Brief Bioinform, 12:5, 392-400, 2011.

Programs

Mathematica

Table[n + Simplify@ Sum[(((n - 2)/(1 + #2^2)) + (2/(#2 - #1))) #1^k + (((#2^2 (n - 2))/(1 + #2^2)) - (2/(#2 - #1))) #2^k + 2, {k, 0, Floor[2 (n - 1)/3]}] & @@ ((1 + Sqrt[5] {1, -1})/2), {n, 53}] (* Michael De Vlieger, Mar 01 2017 *)

Formula

a(n) = n + Sum_{0..k} (((n-2)/(1+Beta^2)) + (2/(Beta-alpha)))alpha^k + (((Beta^2(n-2))/(1+Beta^2)) - (2/(Beta-alpha)))Beta^k + 2 where alpha = (1+sqrt(5))/2, beta = (1-sqrt(5))/2, n = number of letters in each chromosome, and k = floor(2(n-1)/3).

Conjecture: (2 +2*x +3*x^2 -7*x^3 -9*x^4 -6*x^5 +14*x^6 +12*x^7 +7*x^8 -7*x^9 -6*x^10 -3*x^11 +x^13+x^14)/ (1+x+x^2)/ (x-1)^2/ (x^6-3*x^3+1)^2 . - R. J. Mathar, Mar 06 2022

Extensions

More terms from Michael De Vlieger, Mar 01 2017