Please use this identifier to cite or link to this item:

`https://scholarbank.nus.edu.sg/handle/10635/41502`

Title: | Fast algorithms for computing the tripartition-based distance between phylogenetic networks |

Authors: | Nguyen, N.B. Thach Nguyen, C. Sung, W.-K. |

Issue Date: | 2005 |

Citation: | Nguyen, N.B.,Thach Nguyen, C.,Sung, W.-K. (2005). Fast algorithms for computing the tripartition-based distance between phylogenetic networks. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 3827 LNCS : 402-411. ScholarBank@NUS Repository. |

Abstract: | Consider two phylogenetic networks N and N′ of size n. The tripartition-based distance finds the proportion of tripartitions which are not shared by N and N′. This distance is proposed by Moret et al (2004) and is a generalization of Robinson-Foulds distance, which is orginally used to compare two phylogenetic trees. This paper gives an O(min{kn log n, n log n + hn})-time algorithm to compute this distance, where h is the number of hybrid nodes in N and N′ while k is the maximum number of hybrid nodes among all biconnected components in N and N′. Note that k < < h < < in & phylogenetic network. In addition, we propose algorithms for comparing galled-trees, which are an important, biological meaningful special case of phylogenetic network. We give an O(n)-time algorithm for comparing two galled-trees. We also give an O(n + kh)-time algorithm for comparing a galled-tree with another general network, where h and k are the number of hybrid nodes in the latter network and its biggest biconnected component respectively. © Springer-Verlag Berlin Heidelberg 2005. |

Source Title: | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |

URI: | http://scholarbank.nus.edu.sg/handle/10635/41502 |

ISBN: | 3540309357 |

ISSN: | 03029743 |

Appears in Collections: | Staff Publications |

Show full item record

###### Files in This Item:

There are no files associated with this item.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.