Limits...
On the PATHGROUPS approach to rapid small phylogeny.

Zheng C, Sankoff D - BMC Bioinformatics (2011)

Bottom Line: The efficiency of the greedy algorithm is due to fast updating of the structure during run time and a simple priority scheme for choosing the next step.This includes a more refined priority system, and a two-step look-ahead, as well as iterative local improvements based on a the median version of the problem, incorporating simulated annealing.We apply this to a set of yeast genomes to corroborate a recent gene sequence-based phylogeny.

View Article: PubMed Central - HTML - PubMed

Affiliation: Département d'informatique et de recherche opérationnelle, Université de Montréal, Canada. chunfang313@gmail.com

ABSTRACT
We present a data structure enabling rapid heuristic solution to the ancestral genome reconstruction problem for given phylogenies under genomic rearrangement metrics. The efficiency of the greedy algorithm is due to fast updating of the structure during run time and a simple priority scheme for choosing the next step. Since accuracy deteriorates for sets of highly divergent genomes, we investigate strategies for improving accuracy and expanding the range of data sets where accurate reconstructions can be expected. This includes a more refined priority system, and a two-step look-ahead, as well as iterative local improvements based on a the median version of the problem, incorporating simulated annealing. We apply this to a set of yeast genomes to corroborate a recent gene sequence-based phylogeny.

Show MeSH

Related in: MedlinePlus

Representation of the median (left) and more general small phylogeny (right) problems. Grey squares indicate given genomes, red squares those to be reconstructed. Each line connecting two genomes represents a breakpoint graph and a distance.
© Copyright Policy - open-access
Related In: Results  -  Collection


getmorefigures.php?uid=PMC3044296&req=5

Figure 1: Representation of the median (left) and more general small phylogeny (right) problems. Grey squares indicate given genomes, red squares those to be reconstructed. Each line connecting two genomes represents a breakpoint graph and a distance.

Mentions: For a given unrooted binary tree T on N given genomes G1, G2, ⋯, GN (and thus with N – 2 unknown ancestral genomes M1, M2, ⋯, MN–2 and 2N – 3 branches) as depicted in Fig. 1, the small phylogeny problem is to infer the ancestral genomes so that the total edge length of T, namely ∑XY∈E(T)d(X, Y), is minimal.


On the PATHGROUPS approach to rapid small phylogeny.

Zheng C, Sankoff D - BMC Bioinformatics (2011)

Representation of the median (left) and more general small phylogeny (right) problems. Grey squares indicate given genomes, red squares those to be reconstructed. Each line connecting two genomes represents a breakpoint graph and a distance.
© Copyright Policy - open-access
Related In: Results  -  Collection

Show All Figures
getmorefigures.php?uid=PMC3044296&req=5

Figure 1: Representation of the median (left) and more general small phylogeny (right) problems. Grey squares indicate given genomes, red squares those to be reconstructed. Each line connecting two genomes represents a breakpoint graph and a distance.
Mentions: For a given unrooted binary tree T on N given genomes G1, G2, ⋯, GN (and thus with N – 2 unknown ancestral genomes M1, M2, ⋯, MN–2 and 2N – 3 branches) as depicted in Fig. 1, the small phylogeny problem is to infer the ancestral genomes so that the total edge length of T, namely ∑XY∈E(T)d(X, Y), is minimal.

Bottom Line: The efficiency of the greedy algorithm is due to fast updating of the structure during run time and a simple priority scheme for choosing the next step.This includes a more refined priority system, and a two-step look-ahead, as well as iterative local improvements based on a the median version of the problem, incorporating simulated annealing.We apply this to a set of yeast genomes to corroborate a recent gene sequence-based phylogeny.

View Article: PubMed Central - HTML - PubMed

Affiliation: Département d'informatique et de recherche opérationnelle, Université de Montréal, Canada. chunfang313@gmail.com

ABSTRACT
We present a data structure enabling rapid heuristic solution to the ancestral genome reconstruction problem for given phylogenies under genomic rearrangement metrics. The efficiency of the greedy algorithm is due to fast updating of the structure during run time and a simple priority scheme for choosing the next step. Since accuracy deteriorates for sets of highly divergent genomes, we investigate strategies for improving accuracy and expanding the range of data sets where accurate reconstructions can be expected. This includes a more refined priority system, and a two-step look-ahead, as well as iterative local improvements based on a the median version of the problem, incorporating simulated annealing. We apply this to a set of yeast genomes to corroborate a recent gene sequence-based phylogeny.

Show MeSH
Related in: MedlinePlus