Paper Info
Title
Computational modelling of interruptional activities between transposable elements using grammars and the linear ordering problem.
Abstract
Transposable elements (TEs) are DNA sequences that can either move or copy themselves to new positions within a genome. They constitute approximately 45 % of the human genome. Knowing the evolution of TEs is helpful in understanding the activities of these elements and their impacts on genomes. In this paper, we devise a formal model providing notations/definitions that are compatible with biological nomenclature, while still providing a suitable formal foundation for computational analysis. We define sequential interruptions between TEs that occur in a genomic sequence to estimate how often TEs interrupt other TEs, useful in predicting their ages. We also describe the problem in terms of a matrix problem—the linear ordering problem. We then define the recursive interruption context-free grammar to capture the recursive nature in which TEs nest themselves into other TEs, and associate probabilities to convert the context-free grammar into a stochastic context-free grammar, as well as discuss how to use the CYK algorithm to find a most likely parse tree predicting TE nesting. We also discuss improvements on the theoretical model and adjust the parse trees to capture both sequential and recursive interruptional activities between TEs and obtain more standard evolutionary trees.
Year
DOI
Venue
2016
10.1007/s00500-015-1725-2
soft computing
Keywords
Field
DocType
Transposable elements, Formal modelling, Interruptional analysis, Linear ordering problem, Stochastic context-free grammars
Rule-based machine translation,Genome,Notation,Parse tree,CYK algorithm,Computer science,Theoretical computer science,Artificial intelligence,Recursion,Mathematical optimization,Algorithm,Grammar,Parsing,Machine learning
Journal
Volume
Issue
ISSN
20
1
1433-7479
Citations 
PageRank 
References 
0
0.34
8
Authors
2
Name
Order
Citations
PageRank
Lingling Jin100.68
Ian McQuillan29724.72