The combinatorics of tandem duplication

Penso-Dolfin, L., Wu, T. ORCID: https://orcid.org/0000-0002-2663-2001 and Greenman, C. (2015) The combinatorics of tandem duplication. Discrete Applied Mathematics, 194. 1–22. ISSN 0166-218X

	Other (pdf) - Accepted Version Available under License Creative Commons Attribution Non-commercial No Derivatives. Download (2MB)
Preview	PDF (greenman_DAM) - Accepted Version Available under License Creative Commons Attribution Non-commercial No Derivatives. Download (2MB) | Preview

Abstract

Tandem duplication is an evolutionary process whereby a segment of DNA is replicated and proximally inserted. The different configurations that can arise from this process give rise to some interesting combinatorial questions. Firstly, we introduce an algebraic formalism to represent this process as a word producing automaton. The number of words arising from n tandem duplications can then be recursively derived. Secondly, each single word accounts for multiple evolutions. With the aid of a bi-coloured 2d- tree, a Hasse diagram corresponding to a partially ordered set is constructed, from which we can count the number of evolutions corresponding to a given word. Thirdly, we implement some subtree prune and graft operations on this structure to show that the total number of possible evolutions arising from n tandem duplications is $\prod_{k=1}^n(4^k - (2k + 1))$. The space of structures arising from tandem duplication thus grows at a super-exponential rate with leading order term $\mathcal{O}(4^{\frac{1}{2}n^2})$.

Item Type:	Article
Additional Information:	22 Pages, 7 Figures, 1 Table
Uncontrolled Keywords:	combinatorics,tandem duplication,posets,rearrangements,evolution
Faculty \ School:	Faculty of Science > School of Computing Sciences Faculty of Science > School of Natural Sciences (former - to 2024)
UEA Research Groups:	Faculty of Science > Research Groups > Computational Biology Faculty of Science > Research Groups > Computational Biology > Phylogenetics (former - to 2018) Faculty of Science > Research Centres > Centre for Ecology, Evolution and Conservation Faculty of Science > Research Groups > Data Science and AI
Related URLs:	http://arxiv.org/abs/1402.0104
Depositing User:	Pure Connector
Date Deposited:	24 Jul 2015 22:48
Last Modified:	10 Dec 2024 01:25
URI:	https://ueaeprints.uea.ac.uk/id/eprint/53707
DOI:	10.1016/j.dam.2015.05.014

Downloads

Actions (login required)

View Item