WE2.R7.3

On Counting Subsequences and Higher-Order Fibonacci Numbers

Hsin-Po Wang, UC Berkeley, United States; Chi-Wei Chin, Apricob Biomedicals Co Ltd, Taiwan

Session:
Combinatorics and Information Theory 2

Track:
21: Other topics

Location:
VIP

Presentation Time:
Wed, 10 Jul, 12:10 - 12:30

Session Chair:
Shu Liu , University of Electronic Science and Technology of China
Abstract
In array-based DNA synthesis, multiple strands of DNA are synthesized in parallel to reduce the time cost from the sum of their lengths to the length their shortest common supersequences. To maximize the amount of information that can be synthesized into DNA within a finite amount of time, we study the number of unordered sets of n strands of DNA that have a common supersequence whose length is at most t. Our analysis stems from the following connection: The number of subsequences of A C G T A C G T A C G T ... is the partial sum (prefix sum) of the fourth-order Fibonacci numbers.
Resources