## Abstract

In the computational biology and taxonomy, to construct phylogenetic tree is an important problem. A phylogenetic tree can represent the relationship and histories for a set of species and helpful for biologists to observe existent species. One of popular model is ultrametric tree, and it assumed the evolution rate is constant. UPGMA is one of well-known ultrametric tree algorithm. However, UPGMA is a heuristic algorithm, and it can not guarantee the constructed tree is minimum size. To construct minimum ultrametric tree (MUT) has been shown to be an NP-hard problem. In this paper, we propose an efficient parallel branch-and-bound algorithm with 3-Point Relationship (3PR) to reduce the construction time dramatically. 3PR is a relationship between a distance matrix and the constructed phylogenetic tree. The main concept is for any two species closed to each other in a distance matrix should be also closed to each other in the constructed phylogenetic tree. We use this property to mark the branching path with lower priority or higher, then we move the lower ranked branching path to delay bound pool instead of remove it to ensure the optimal solution can be found. The experimental results show that our parallel algorithm can save the computing time and it also shows that parallel algorithm with 3PR can save about 25% of computing time in average.

Original language | English |
---|---|

Title of host publication | Frontiers of High Performance Computing and Networking - ISPA 2006 International Workshops, FHPCN, XHPC, S-GRACE, GridGIS, HPC-GTP, PDCE, ParDMCom, WOMP, ISDF, and UPWN, Proceedings |

Pages | 215-220 |

Number of pages | 6 |

DOIs | |

State | Published - 2006 |

Externally published | Yes |

Event | Int. Workshops on FHPCN 2006, XHPC 2006, S-GRACE 2006, GridGIS 2006, HPC-GTP 2006, PDCE 2006, ParDMCom 2006, WOMP 2006, ISDF 2006, and UPWN 2006, Held in Conjunction with the 4th Int. Symp. on Parallel and Distributed Processing and Appl., SPA 2006 - Sorrento, Italy Duration: 04 12 2006 → 07 12 2006 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 4331 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | Int. Workshops on FHPCN 2006, XHPC 2006, S-GRACE 2006, GridGIS 2006, HPC-GTP 2006, PDCE 2006, ParDMCom 2006, WOMP 2006, ISDF 2006, and UPWN 2006, Held in Conjunction with the 4th Int. Symp. on Parallel and Distributed Processing and Appl., SPA 2006 |
---|---|

Country/Territory | Italy |

City | Sorrento |

Period | 04/12/06 → 07/12/06 |

## Keywords

- 3-point relationship
- 4-point relationship
- Minimum ultrametric tree
- Parallel branch-and-bound algorithm
- Phylogenetic tree