Back to results
US 7,254,489 B2Granted
Systems, methods and apparatus for reconstructing phylogentic trees
AssigneeMicrosoft Corporation
InventorElchanan Mossel
Life of this patent
Estimating the term…
Abstract
In one aspect, a tree data structure is reconstructed by reconstructing a local topology from samples of data of known nodes, and estimating the data value of each node in the reconstructed local topology. The reconstructing and estimating are performed iteratively. In another aspect, the topology is reconstructed from pairs of known nodes that are within a predetermined correlation, and using a four-point function. The number of samples of data that the topology is calculated from is a factor of a natural logarithm of the number of known nodes that are within a predetermined correlation. In another aspect, the estimating is performed using a majority function.
Claims35
One or more computer-readable media comprising computer executable instructions that, when executed, direct a computing system to perform a method comprising:
- reconstructing a predicted phylogenetic tree topology by:
- determining samples of characters of a plurality of known nodes;
- identifying each of the samples including a number of characters;
- calculating the number of characters being approximately equal to a factor of a natural logarithm of the number of the plurality of known nodes,
- selecting one or more of the plurality of known nodes that are within a predetermined threshold;
- yielding a reconstructed phylogenetic tree topology having one or more reconstructed nodes based on the selecting one or more of the plurality of known nodes;
- estimating a sequence of characters of each of the one or more nodes in the reconstructed phylogenetic tree topology in accordance with a stochastic mutation model using a majority function;
- presenting the reconstructed predicted phylogenetic tree topology;
- and
- determining closeness of relationship between species or individuals, based on the reconstructed phylogenetic tree topology.
7 more elements
A computer-based method of reconstructing an entire phylogenetic tree from a plurality of known leaf nodes of the phylogenetic tree, the method comprising:
- reconstructing one or more levels of a predicted phylogenetic tree topology from samples of characters of the plurality of known leaf nodes by:
- determining the samples including a number of characters,
- calculating the number of characters being approximately equal to a factor of a natural logarithm of the number of the plurality of known leaf nodes,
- selecting one or more known leaf nodes that are within a predetermined threshold;
- yielding a reconstructed partial phylogenetic tree topology having at least one leaf node based on the selecting one or more known leaf nodes;
- estimating characters of each of the at least one leaf node in the reconstructed partial phylogenetic tree topology in accordance with a stochastic mutation model;
- performing the reconstructing and the estimating iteratively to reconstruct node topology and estimate node characters for successively higher levels of the predicted phylogenetic tree topology until the entire phylogenetic tree is reconstructed;
- presenting the reconstructed predicted phylogenetic tree;
- and
- determining closeness of relationship between species or individuals, based on the reconstructed phylogenetic tree.
7 more elements
A computer-based method of reconstructing an entire phylogenetic tree from a plurality of known leaf nodes of the phylogenetic tree, the method comprising:
- reconstructing one or more levels of a predicted phylogenetic tree from samples of characters of the plurality of known leaf nodes;
- identifying one or more pairs of the plurality of known leaf nodes from samples of characters of each of the plurality of known leaf nodes, wherein each of the samples include a number of characters,
- calculating the number of characters being approximately equal to a factor of a natural logarithm of the number of the plurality of known leaf nodes;
- calculating a distance for each of the one or more identified pairs of the plurality of known leaf nodes from the samples of characters of the one or more identified pairs;
- selecting one or more of the identified pairs of the plurality of known leaf nodes that are within a predetermined threshold distance;
- yielding one or more levels of a reconstructed predicted phylogenetic tree topology from the samples of the characters of the selected pairs of known leaf nodes, the reconstructed phylogenetic tree structure having at least one node;
- estimating characters of each of the at least one node in the reconstructed phylogenetic tree topology;
- performing the reconstructing and the estimating iteratively to reconstruct node topology and estimate node characters for successively higher levels of the reconstructed tree topology until the entire phylogenetic tree is reconstructed;
- presenting the reconstructed tree topology to an end-user;
- and
- determining closeness of relationship between species or individuals, based on the reconstructed phylogenetic tree topology.
8 more elements
A computer-based method of reconstructing a tree from a plurality of known leaf nodes of the phylogenetic tree, each known node having characters, the method comprising:
- reconstructing a predicted phylogenetic tree topology from samples of the characters of each of the plurality of known leaf nodes by,
- identifying each of the samples including a number of characters;
- calculating the number of characters being approximately equal to a factor of a natural logarithm of the number of the plurality of known leaf nodes;
- selecting one or more known leaf nodes that are within a predetermined threshold;
- yielding a reconstructed phylogenetic tree topology having one or more nodes;
- estimating a sequence of characters of each of the one or more nodes in the reconstructed phylogenetic tree topology in accordance with a stochastic mutation model using a majority function;
- presenting the reconstructed predicted phylogenetic tree;
- and
- determining closeness of relationship between species or individuals, based on the reconstructed phylogenetic tree topology.
6 more elements
A system to reconstruct an entire tree from a plurality of known leaf nodes of the tree:
- a processor;
- and
- a memory to store the plurality of known leaf nodes of the phylogenetic tree, each known leaf node having characters, and the memory containing instructions that causes the processor to perform actions comprising:
- reconstructing one or more levels of a predicted phylogenetic tree topology from samples of the characters of each of the plurality of known leaf nodes by:
- identifying each of the samples including a number of characters;
- calculating the number of characters being approximately equal to a factor of a natural logarithm of the number of the plurality of known nodes;
- yielding a reconstructed partial phylogenetic tree topology having at least one leaf node;
- and
- estimating characters of each of the at least one leaf node in the reconstructed partial phylogenetic tree topology in accordance with a stochastic mutation model;
- performing the reconstructing and the estimating iteratively to reconstruct node topology and estimate node characters for successively higher levels of the reconstructed tree topology until the entire phylogenetic tree is reconstructed;
- and
- a display device to present the reconstructed predicted phylogenetic tree in determining closeness of relationship between species or individuals, based on the reconstructed phylogenetic tree topology.
9 more elements
A system to reconstruct an entire phylogenetic tree from a plurality of known leaf nodes of the tree:
- a processor;
- and
- a memory to store the plurality of known leaf nodes of the phylogenetic tree, each known leaf node having characters, and containing instructions that causes the processor to perform actions comprising:
- reconstructing one or more levels of a phylogenetic tree topology from samples of the characters of the plurality of known leaf nodes by:
- identifying one or more pairs of the plurality of known leaf nodes from samples of the characters, the samples including a number of characters;
- calculating the number of characters being approximately equal to a factor of a natural logarithm of the number of the plurality of known leaf nodes;
- calculating a distance for each of the one or more identified pairs from the samples of characters of the one or more identified pairs;
- selecting one or more identified pairs that are within a predetermined threshold distance;
- and
- yielding a reconstructed predicted phylogenetic tree topology from samples of the characters of the one or more selected pairs;
- estimating characters of each of the reconstructed nodes in the reconstructed phylogenetic tree topology in accordance with a stochastic mutation model;
- performing the reconstructing and the estimating iteratively to reconstruct node topology and estimate node characters for successively higher levels of the reconstructed tree topology until the entire phylogenetic tree is reconstructed;
- and
- a display device to present the reconstructed predicted phylogenetic tree in determining closeness of relationship between species or individuals, based on the reconstructed phylogenetic tree topology.
11 more elements
A system to reconstruct a tree from a plurality of known leaf nodes of the tree:
- a processor;
- and
- a memory to store the plurality of known leaf nodes of the phylogenetic tree, each known leaf node having a sequence of characters, the memory containing instructions that causes the processor to perform actions comprising:
- reconstructing a predicted phylogenetic tree topology from samples of the sequence of characters of each of the plurality of known leaf nodes by:
- identifying each of the samples including a number of characters;
- calculating the number of characters being approximately equal to a factor of a natural logarithm of the number of the plurality of known nodes;
- yielding a reconstructed phylogenetic tree topology having one or more nodes;
- estimating a sequence of characters of each of the one or more nodes in the reconstructed phylogenetic tree topology in accordance with a stochastic mutation model from a majority function;
- and
- a display device to present the reconstructed phylogenetic tree topology to represent an evolution in determining how closely related species or individuals are, based on the reconstructed phylogenetic tree.
7 more elements
Dependencies are inferred from the claim text.