Unicyclic Networks: Compatibility and Enumeration (2006)
AuthorsSemple, C., Steel, M.show all
Graphs obtained from a binary leaf labelled (‘phylogenetic’) tree by adding an edge so as to introduce a cycle provide a useful representation of hybrid evolution in molecular evolutionary biology. This class of graphs (which we call ‘unicyclic networks’) also has some attractive combinatorial properties, which we present. We characterize when a set of binary phylogenetic trees is displayed by a unicyclic network in terms of tree rearrangement operations. This leads to a triple-wise compatibility theorem, and a simple, fast algorithm to determine 1-cycle compatibility. We also use generating function techniques to provide closed-form expressions that enumerate unicyclic networks with specified or unspecified cycle length, and we provide an extension to enumerate a class of multi-cyclic networks.
CitationSemple, C., Steel, M. (2006) Unicyclic Networks: Compatibility and Enumeration. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 3(1), pp. 84-91.
This citation is automatically generated and may be unreliable. Use as a guide only.