Presentation | 2005-01-28 Inferring Pedigrees from Genetic Distances Takeyuki TAMURA, Hiro ITO, Kazuo IWAMA, |
---|---|
PDF Download Page | PDF download Page Link |
Abstract(in Japanese) | (See Japanese page) |
Abstract(in English) | A phylogenetic tree is a tree data structure which shows evolutionary interrelationships among species which are believed to have a common ancestor. Numerous methods of inferring phylogenetic trees from genetic information have been researched. Moreover, some data structures which are slightly different from phylogenetic trees have been proposed to infer. On the other hand, pedigrees can be regarded as more informed phylogenetic trees. Phylogenetic trees can be represented by directed trees, whereas pedigrees are represented by directed acyclic graphs whose indegrees are at most two. In this paper, we deal with a problem in which our algorithm enumerates all pedigrees which satisfy given genetic distances between two nodes. We show that the output pedigrees can be represented by one directed graph without increasing the number of nodes. Moreover, O(n^3)-time algorithm which solves the problem is also given. |
Keyword(in Japanese) | (See Japanese page) |
Keyword(in English) | distance matrix / pedigree / genetic distance / phylogenetic tree / and phylogenetic network |
Paper # | COMP2004-64 |
Date of Issue |
Conference Information | |
Committee | COMP |
---|---|
Conference Date | 2005/1/21(1days) |
Place (in Japanese) | (See Japanese page) |
Place (in English) | |
Topics (in Japanese) | (See Japanese page) |
Topics (in English) | |
Chair | |
Vice Chair | |
Secretary | |
Assistant |
Paper Information | |
Registration To | Theoretical Foundations of Computing (COMP) |
---|---|
Language | JPN |
Title (in Japanese) | (See Japanese page) |
Sub Title (in Japanese) | (See Japanese page) |
Title (in English) | Inferring Pedigrees from Genetic Distances |
Sub Title (in English) | |
Keyword(1) | distance matrix |
Keyword(2) | pedigree |
Keyword(3) | genetic distance |
Keyword(4) | phylogenetic tree |
Keyword(5) | and phylogenetic network |
1st Author's Name | Takeyuki TAMURA |
1st Author's Affiliation | School of Informatics, Kyoto University() |
2nd Author's Name | Hiro ITO |
2nd Author's Affiliation | School of Informatics, Kyoto University |
3rd Author's Name | Kazuo IWAMA |
3rd Author's Affiliation | School of Informatics, Kyoto University |
Date | 2005-01-28 |
Paper # | COMP2004-64 |
Volume (vol) | vol.104 |
Number (no) | 642 |
Page | pp.pp.- |
#Pages | 7 |
Date of Issue |