Resolve Polytomies Using Parsimony-Based Reconstruction of a Discrete Character

Description

This function resolves a set of given topology with less than fully-binary phylogenetic resolution so that lineages are shifted and internal nodes added that minimize the number of independent character transitions needed to explain an observed distribution of discrete character states for the taxa on such a tree, under various maximum-parsimony algorithms of ancestral character reconstruction, powered ultimately by function ancestral.pars in library phangorn. This function is mainly designed for use with poorly resolved trees which are being assessed with the function minCharChange.

Usage

1
2
3
resolveTreeChar(tree, trait, orderedChar = FALSE, stateBias = NULL,
  iterative = TRUE, type = "MPR", cost = NULL, ambiguity = c(NA, "?"),
  dropAmbiguity = FALSE, polySymbol = "&", contrast = NULL)

Arguments

tree

A cladogram of type 'phylo'. Any branch lengths are ignored.

trait

A vector of trait values for a discrete character, preferably named with taxon names identical to the tip labels on the input tree.

orderedChar

Is the character of interest given for trait ordered or not? If FALSE (the default), then for each polytomy, all child nodes that appear to have the same state as the ancestor node will remain in the polytomy, and any additional states held by child nodes will each be grouped into their own unique polytomy that forms from a descendant node of the original polytomy. If TRUE, then the character will be reconstructed with a cost (step) matrix of a linear, ordered character, and polytomies will be resolved so that lineages with different states will be placed into a nested ladder that reflects the ordered character. As with the unordered option, child nodes with a state equivalent to the ancestral node will remain in the polytomy, while more primitive or more derived states will be sorted into their own separate ladders composed of paraphyletic groups, ordered so to move 'away' state-by-state from the ancestral node's inferred character state. This option is not applicable if type = "ACCTRAN", as cost matrices cannot be used with ACCTRAN in ancestral.pars, and an error will be returned if orderedChar=TRUE but a cost matrix is given manually.

stateBias

This argument controls how resolveTreeChar handles ancestral node reconstructions that have multiple states competing for the maximum weight of any state (i.e. if states 0 and 1 both have 0.4 of the weight). The default, where stateBias = NULL causes uncertainty at nodes among states to be treated as a single 'group' identical to any states within it. Essentially, this means that for the example polytomy where the ancestor hax maximum weight for both 0 and 1, any child nodes with 0, 1 or both of these states will be considered to have an identical state for the purpose of grouping nodes for the purpose of further resolving polytomies. If and only if orderedChar = TRUE, then additional options of stateBias = 'primitive' and stateBias = 'derived' become available, which instead force uncertain node assignments to either be the most primitive (i.e. the minimum) or the most derived (i.e. the maximum) among the maximum-weight states. In particular, stateBias = 'primitive' should favor gains and bias any analysis of character transitions against finding reversals.

iterative

A logical argument which, if TRUE (the default), causes the function to repeat the polytomy-resolving functionality across the entire tree until the number of nodes stabilizes. If FALSE, polytomies are only passed a single time.

type

The parsimony algorithm applied by ancestral.pars, which can apply one of two: "MPR" (the default) is a relatively fast algorithm developed by Hamazawa et al. (1995) and Narushima and Hanazawa (1997), which relies on reconstructing the states at each internal node by re-rooting at that node. "ACCTRAN", the 'accelerated transitions' algorithm (Swofford and Maddison, 1987), favors character reversal over independent gains when there is ambiguity. The "ACCTRAN" option in ancestral.pars avoids repeated rerooting of the tree to search for a smaller set of maximum-parsimony solutions that satisfy the ACCTRAN algorithm, but does so by assigning edge weights. As of phangorn v1.99-12, both of these algorithms apply the Sankoff parsimony algorithm, which allows multifurcations (polytomies).

cost

A matrix of the cost (i.e. number of steps) necessary to change between states of the input character trait. If NULL (the default), the character is assumed to be unordered with equal cost to change from any state to another. Cost matrices only impact the "MPR" algorithm; if a cost matrix is given but type = "ACCTRAN", an error is issued.

ambiguity

A vector of values which indicate ambiguous (i.e. missing or unknown) character state codings in supplied trait data. Taxa coded ambiguously as treated as being equally likely to be any state coding. By default, NA values and "?" symbols are treated as ambiguous character codings, in agreement with behavior of functions in packages phangorn and Claddis. This argument is designed to mirror an hidden argument with an identical name in function phyDat in package phangorn.

dropAmbiguity

A logical. If TRUE (which is not the default), all taxa with ambiguous codings as defined by argument ambiguity will be dropped prior to ancestral nodes being inferred. This may result in too few taxa.

polySymbol

A single symbol which separates alternative states for polymorphic codings; the default symbol is "&", following the output by Claddis's ReadMorphNexus function, where polymorphic taxa are indicated by default with a string with state labels separated by an "&" symbol. For example, a taxon coded as polymorphic for states 1 or 2, would be indicated by the string "1&2". polySymbol is used to break up these strings and automatically construct a fitting contrast table for use with this data, including for ambiguous character state codings.

contrast

A matrix of type integer with cells of 0 and 1, where each row is labelled with a string value used for indicating character states in trait, and each column is labelled with the formal state label to be used for assign taxa to particular character states. A value of 1 indicates that the respective coding string for that row should be interpreted as reflecting the character state listed for that column. A coding could reflect multiple states (such as might occur when taxa are polymorphic for some morphological character), so the sums of rows and columns can sum to more than 1. If contrast is not NULL (the default), the arguments will nullify This argument is designed to mirror an hidden argument with an identical name in function phyDat in package phangorn. This structure is based on the contrasts tables used for statistical evaluation of factors. See the phangorn vignette "Special features of phangorn" for more details on its implementation within phangorn including an example. See examples below for the construction of an example contrast matrix for character data with polymorphisms, coded as character data output by Claddis's ReadMorphNexus function, where polymorphic taxa are indicated with a string with state labels separated by an "&" symbol.

Details

As shown in the example code below, this function offers a wide variety of options for manipulating the maximum-parsimony algorithm used (i.e. MPR versus ACCTRAN), the ordering (or not) of character states, and potential biasing of uncertainty character state reconstructions (when ordered characters are assessed). This allows for a wide variety of possible resolutions for a given tree with polytomies and a discrete character. In general, the author expects that use of this function will be optimal when applied to ordered characters using one of the stateBias options, perhaps stateBias = "primitive" (based on theoretical expectations for slow evolving characters). However, anecdotal use of this function with various simulation datasets suggests that the results are quite variable, and so the best option needs to be assessed based on the prior assumptions regarding the data and the performance of the dataset with the various arguments of this function.

Value

Returns the resulting tree, which may be fully resolved, partly more resolved or not more resolved at all (i.e. have less polytomies) depending on what was possible, as constrained by ambiguities in character reconstructions. Applying multi2di is suggested as a post-step to obtain a fully-resolved cladogram, if one is desired.

Author(s)

David W. Bapst

References

Hanazawa, M., H. Narushima, and N. Minaka. 1995. Generating most parsimonious reconstructions on a tree: A generalization of the Farris-Swofford-Maddison method. Discrete Applied Mathematics 56(2-3):245-265.

Narushima, H., and M. Hanazawa. 1997. A more efficient algorithm for MPR problems in phylogeny. Discrete Applied Mathematics 80(2-3):231-238.

Schliep, K. P. 2011. phangorn: phylogenetic analysis in R. Bioinformatics 27(4):592-593.

Swofford, D. L., and W. P. Maddison. 1987. Reconstructing ancestral character states under Wagner parsimony. Mathematical Biosciences 87(2):199-229.

See Also

ancPropStateMat which is used internally by this function. This function was intentionally designed for use with minCharChange.

Examples

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
# let's write a quick&dirty ancestral trait plotting function

 quickAncPlot<-function(tree,trait,cex,orderedChar=FALSE,type="MPR",cost=NULL){
	ancData<-ancPropStateMat(tree=tree, trait=trait, orderedChar=orderedChar)
	ancCol<-(1:ncol(ancData))+1
 	plot(tree,show.tip.label=FALSE,no.margin=TRUE,direction="upwards")
 	tiplabels(pch=16,pie=ancData[(1:Ntip(tree)),],cex=cex,piecol=ancCol,
		col=0)
 	nodelabels(pie=ancData[-(1:Ntip(tree)),],cex=cex,piecol=ancCol)	
 	}

##########

# examples with simulated data

set.seed(2)
tree<-rtree(50)
#simulate under a likelihood model
trait<-rTraitDisc(tree,k=3,rate=0.7)
tree<-degradeTree(tree,prop_collapse=0.6)
tree<-ladderize(tree,right=FALSE)

#a bunch of type=MPR (default) examples
treeUnord<-resolveTreeChar(tree,trait,orderedChar=FALSE)
treeOrd<-resolveTreeChar(tree,trait,orderedChar=TRUE,stateBias=NULL)
treeOrdPrim<-resolveTreeChar(tree,trait,orderedChar=TRUE,stateBias="primitive")
treeOrdDer<-resolveTreeChar(tree,trait,orderedChar=TRUE,stateBias="derived")
#and finally an unordered one with ACCTRAN
treeACCTRAN<-resolveTreeChar(tree,trait,orderedChar=FALSE,type="ACCTRAN")

#compare number of nodes
Nnode(tree)			#original
Nnode(treeUnord)		#unordered, biasStates=NULL, MPR
Nnode(treeOrd)		#ordered, biasStates=NULL
Nnode(treeOrdPrim)	#ordered, biasStates='primitive'
Nnode(treeOrdDer)	#ordered, biasStates='derived'
Nnode(treeACCTRAN)	#unordered, biasStates=NULL, ACCTRAN

#let's compare original tree with unordered-resolved tree
layout(1:2)
quickAncPlot(tree,trait,orderedChar=FALSE,cex=0.3)
text(x=43,y=10,"Original",cex=1.5)
quickAncPlot(treeUnord,trait,orderedChar=FALSE,cex=0.3)
text(x=43,y=10,"orderedChar=FALSE",cex=1.5)
#some resolution gained

#now let's compare the original and ordered, both biasStates=NULL
layout(1:2)
quickAncPlot(tree,trait,orderedChar=FALSE,cex=0.3)
text(x=43,y=10,"Original",cex=1.5)
quickAncPlot(treeOrd,trait,orderedChar=TRUE,cex=0.3)
text(x=43,y=10,"orderedChar=TRUE",cex=1.5)

#now let's compare the three ordered trees
layout(1:3)
quickAncPlot(treeOrd,trait,orderedChar=TRUE,cex=0.3)
text(x=41,y=8,"ordered, biasStates=NULL",cex=1.5)
quickAncPlot(treeOrdPrim,trait,orderedChar=TRUE,cex=0.3)
text(x=41.5,y=8,"ordered, biasStates='primitive'",cex=1.5)
quickAncPlot(treeOrdDer,trait,orderedChar=TRUE,cex=0.3)
text(x=42,y=8,"ordered, biasStates='derived'",cex=1.5)

#let's compare unordered with ordered, biasStates='primitive'
layout(1:2)
quickAncPlot(treeUnord,trait,orderedChar=FALSE,cex=0.3)
text(x=41,y=8,"orderedChar=FALSE",cex=1.5)
quickAncPlot(treeOrdPrim,trait,orderedChar=TRUE,cex=0.3)
text(x=40,y=11,"orderedChar=TRUE",cex=1.5)
text(x=40,y=4,"biasStates='primitive'",cex=1.5)

#let's compare unordered with MPR to unordered with ACCTRAN
layout(1:2)
quickAncPlot(treeUnord,trait,orderedChar=FALSE,type="MPR",cex=0.3)
text(x=41,y=8,"unordered: MPR",cex=1.5)
quickAncPlot(treeACCTRAN,trait,orderedChar=FALSE,type="ACCTRAN",cex=0.3)
text(x=41,y=8,"unordered: ACCTRAN",cex=1.5)

#these comparisons will differ greatly between datasets
	# need to try them on your own

layout(1)

Want to suggest features or report bugs for rdrr.io? Use the GitHub issue tracker.