Constructing perfect phylogenies and proper triangulations for three-state characters
<p>Abstract</p> <p/> <p>In this paper, we study the problem of constructing perfect phylogenies for three-state characters. Our work builds on two recent results. The first result states that for three-state characters, the local condition of examining all subsets of three ch...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
BMC
2012-09-01
|
| Series: | Algorithms for Molecular Biology |
| Subjects: | |
| Online Access: | http://www.almob.org/content/7/1/26 |
| _version_ | 1811286427822981120 |
|---|---|
| author | Gysel Rob Lam Fumei Gusfield Dan |
| author_facet | Gysel Rob Lam Fumei Gusfield Dan |
| author_sort | Gysel Rob |
| collection | DOAJ |
| description | <p>Abstract</p> <p/> <p>In this paper, we study the problem of constructing perfect phylogenies for three-state characters. Our work builds on two recent results. The first result states that for three-state characters, the local condition of examining all subsets of three characters is sufficient to determine the global property of admitting a perfect phylogeny. The second result applies tools from minimal triangulation theory to the partition intersection graph to determine if a perfect phylogeny exists. Despite the wealth of combinatorial tools and algorithms stemming from the chordal graph and minimal triangulation literature, it is unclear how to use such approaches to efficiently construct a perfect phylogeny for three-state characters when the data admits one. We utilize structural properties of both the partition intersection graph and the original data in order to achieve a competitive time bound.</p> |
| first_indexed | 2024-04-13T02:59:47Z |
| format | Article |
| id | doaj.art-6d12b49e376941dfbb93feab20e931b1 |
| institution | Directory Open Access Journal |
| issn | 1748-7188 |
| language | English |
| last_indexed | 2024-04-13T02:59:47Z |
| publishDate | 2012-09-01 |
| publisher | BMC |
| record_format | Article |
| series | Algorithms for Molecular Biology |
| spelling | doaj.art-6d12b49e376941dfbb93feab20e931b12022-12-22T03:05:28ZengBMCAlgorithms for Molecular Biology1748-71882012-09-01712610.1186/1748-7188-7-26Constructing perfect phylogenies and proper triangulations for three-state charactersGysel RobLam FumeiGusfield Dan<p>Abstract</p> <p/> <p>In this paper, we study the problem of constructing perfect phylogenies for three-state characters. Our work builds on two recent results. The first result states that for three-state characters, the local condition of examining all subsets of three characters is sufficient to determine the global property of admitting a perfect phylogeny. The second result applies tools from minimal triangulation theory to the partition intersection graph to determine if a perfect phylogeny exists. Despite the wealth of combinatorial tools and algorithms stemming from the chordal graph and minimal triangulation literature, it is unclear how to use such approaches to efficiently construct a perfect phylogeny for three-state characters when the data admits one. We utilize structural properties of both the partition intersection graph and the original data in order to achieve a competitive time bound.</p>http://www.almob.org/content/7/1/26Perfect phylogenyChordal graphMinimal triangulationMinimal separator |
| spellingShingle | Gysel Rob Lam Fumei Gusfield Dan Constructing perfect phylogenies and proper triangulations for three-state characters Algorithms for Molecular Biology Perfect phylogeny Chordal graph Minimal triangulation Minimal separator |
| title | Constructing perfect phylogenies and proper triangulations for three-state characters |
| title_full | Constructing perfect phylogenies and proper triangulations for three-state characters |
| title_fullStr | Constructing perfect phylogenies and proper triangulations for three-state characters |
| title_full_unstemmed | Constructing perfect phylogenies and proper triangulations for three-state characters |
| title_short | Constructing perfect phylogenies and proper triangulations for three-state characters |
| title_sort | constructing perfect phylogenies and proper triangulations for three state characters |
| topic | Perfect phylogeny Chordal graph Minimal triangulation Minimal separator |
| url | http://www.almob.org/content/7/1/26 |
| work_keys_str_mv | AT gyselrob constructingperfectphylogeniesandpropertriangulationsforthreestatecharacters AT lamfumei constructingperfectphylogeniesandpropertriangulationsforthreestatecharacters AT gusfielddan constructingperfectphylogeniesandpropertriangulationsforthreestatecharacters |