Generation of Neuronal Trees by a New Three Letters Encoding

Authors

  • Mahdi Amani Department of Computer Science, School of Mathematics, Statistics, and Computer Science, University of Tehran, Tehran & Institute for Studies in Theoretical Physics and Mathematics (I.P.M.), Tehran
  • Abbas Nowzari-Dalini Department of Computer Science, School of Mathematics, Statistics, and Computer Science, University of Tehran, Tehran & Institute for Studies in Theoretical Physics and Mathematics (I.P.M.), Tehran
  • Hayedeh Ahrabian Department of Computer Science, School of Mathematics, Statistics, and Computer Science, University of Tehran, Tehran & Institute for Studies in Theoretical Physics and Mathematics (I.P.M.), Tehran

Keywords:

Neuronal tree, evolutionary tree, phylogenetic tree, tree of life, cladistic rooted tree, generation algorithm, ranking and unranking algorithms

Abstract

A neuronal tree is a rooted tree with n leaves whose each internal node has at least two children; this class not only is defined based on the structure of dendrites in neurons, but also refers to phylogenetic trees or evolutionary trees. More precisely, neuronal trees are rooted-multistate phylogenetic trees whose size is defined as the number of leaves. In this paper, a new encoding over an alphabet of size 3 (minimal cardinality) is introduced for representing the neuronal trees with a given number of leaves. This encoding is used for generating neuronal trees with n leaves in A-order with constant average time and O(n) time complexity in the worst case. Also, new ranking and unranking algorithms are presented in time complexity of O(n) and O(n log n), respectively.

Downloads

Download data is not yet available.

Downloads

How to Cite

Amani, M., Nowzari-Dalini, A., & Ahrabian, H. (2015). Generation of Neuronal Trees by a New Three Letters Encoding. Computing and Informatics, 33(6), 1428–1450. Retrieved from https://www.cai.sk/ojs/index.php/cai/article/view/2820