tree

package
v0.4.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Mar 9, 2020 License: GPL-2.0 Imports: 18 Imported by: 6

Documentation

Overview

Package gotree implements a simple library for handling phylogenetic trees in go

Index

Constants

View Source 
const (
	NIL_SUPPORT = -1.0
	NIL_LENGTH  = -1.0
	NIL_PVALUE  = -1.0
	NIL_ID      = -1
	NIL_TIPID   = 0
)

Constant for uninitialized values

View Source 
const (
	QUARTET_EQUALS = iota
	QUARTET_CONFLICT
	QUARTET_DIFF
)
View Source 
const MaxInt = int(^uint(0) >> 1)
View Source 
const (
	NIL_DEPTH = -1
)

Uninitialized depth is coded as -1

Variables

This section is empty.

Functions

func CommonEdges 

func CommonEdges(edges1 []*Edge, edges2 []*Edge, tipEdges bool) (tree1 int, common int, err error)

This function compares 2 trees and returns the number of edges in common.

It does not check if the trees have different sets of tip names, but just compare the bitsets. If called on two trees with the same number of tips with different names, it will give meaningless results.

It assumes that functions 

tree.UpdateTipIndex()
tree.ClearBitSets()
tree.UpdateBitSet()

Have been called before, otherwise will output an error

If tipedges is false: does not take into account tip edges

func Compare added in v0.2.0 

func Compare(refTree *Tree, compTrees <-chan Trees, tips, comparetreeidentical bool, cpus int) (<-chan BipartitionStats, error)

This function compares bipartitions of a reference tree with a set of trees given in the input channel.

If tips is true, then comparison includes external branches. If comparetreeidentical is true, does not compute the exact number of common and specific branches, but just put sametree=true or sametree=false in the stat channel.

This function returns almost immediately because computation is done in several go routines in background. However it returns a Channel that will contain bipartition statistics computed so far. This channel is closed at the end of the computations, so on the calling functin, you can iterate over this channel in order to wait for the end of computations.

It First Initializes bitsets of the reference tree

func NewAllNodeIndex added in v0.2.9 

func NewAllNodeIndex(t *Tree) *nodeIndex

Tips + internal nodes

func NewNodeIndex 

func NewNodeIndex(t *Tree) (*nodeIndex, error)

Only Tips Computes a node index for a given tree.

Types

type BipartitionStats added in v0.2.0 

type BipartitionStats struct {
	Id       int   // Identifier of the tree analyzed
	Tree1    int   // Number of bipartitions specific to the first tree
	Tree2    int   // Number of bipartitions specific to the second tree
	Common   int   // Number of common bipartitions specific to the second tree
	Sametree bool  // True if the trees are identical
	Err      error // Wether an error occured or not in the computation
}

Type for channel of tree stats

type Edge 

type Edge struct {
	// contains filtered or unexported fields
}

Structure of an edge

func MaxLengthPath added in v0.1.6 

func MaxLengthPath(cur *Node, prev *Node) ([]*Edge, float64, error)

Computes the path of maximum length between the given node and any other node.

It takes as argument the node from which we want to get the farthest tip (longest possible path).

It returns the path (slice of edges), and the sum of branch lengths of this path.

Returns an error if a branch has no length

func (*Edge) AddComment added in v0.2.7 

func (e *Edge) AddComment(comment string)

Adds a comment to the edge. It will be coded by a list of [] In the Newick format.

func (*Edge) Bitset 

func (e *Edge) Bitset() *bitset.BitSet

Returns the BitSet of that edge. It may be nil if not initialized.

the ith bit corresponds position of tip i around the branch (left:0/right:1).

i is the index of the tip in the sorted tip name array

func (*Edge) ClearComments added in v0.2.7 

func (e *Edge) ClearComments()

Removes all comments associated to the node

func (*Edge) Comments added in v0.2.7 

func (e *Edge) Comments() []string

Returns the list of comments associated to the edge.

func (*Edge) CommentsString added in v0.2.7 

func (e *Edge) CommentsString() string

Returns the string of comma separated comments surounded by [].

func (*Edge) DumpBitSet 

func (e *Edge) DumpBitSet() string

Returns a string representing the bitset (bipartition) defined by this edge

func (*Edge) FindEdge 

func (e *Edge) FindEdge(edges []*Edge) (*Edge, error)

Return the given edge in the array of edges comparing bitsets fields Return nil if not found.

Bitsets must be initialized otherwise returns an error.

func (*Edge) HashCode added in v0.4.0 

func (e *Edge) HashCode() uint64

HashCode for an Edge

Used for insertion in an HashMap If the bitsets are not initialized, then returns 0

func (*Edge) HashEquals added in v0.4.0 

func (e *Edge) HashEquals(h hashmap.Hasher) bool

HashCode for an edge bitset.

Used for insertion in an EdgeMap

func (*Edge) Id 

func (e *Edge) Id() int

Returns the Id of the branch.

Returns an error if not initialized.

func (*Edge) IncrementSupport added in v0.4.0 

func (e *Edge) IncrementSupport(support float64)

Increments the branch support by the given support

func (*Edge) Inverse added in v0.4.0 

func (e *Edge) Inverse()

Inverse Edge orientation: left becomes right and right becomes left

func (*Edge) Left 

func (e *Edge) Left() *Node

Returns the node at the left side of the edge (parent)

func (*Edge) Length 

func (e *Edge) Length() float64

returns the length of the branch

func (*Edge) LengthString added in v0.2.1 

func (e *Edge) LengthString() string

Returns the length as a string representing the right precision float (not 0.010000000 but 0.01 for example)

func (*Edge) Locality added in v0.1.8 

func (e *Edge) Locality(maxdist int, cutoff float64) (float64, float64, float64, bool, bool)

Returns the average difference and the max difference in support between the current edge and its neighbors.

The neighbors are defined by the branches located in a area defined by number of branches separating them (<d).

  • cutoff: Cutoff to consider hx=true or hy=true
  • hx=true if exists a neighbor branch with suppt > cutoff
  • hy=true if the current branch has suppt > cutoff */

Returns (avg diff, min diff, max diff, hx, hy)

func (*Edge) Name added in v0.2.1 

func (e *Edge) Name(rooted bool) (nodename string)

Returns the name associated to this Edge.

If rooted, the output clade name is the name of the descendent node.

Else, the clade name is the name of the node on the lightest side. In that case bitsets need to be initialized.

func (*Edge) NeigborEdges added in v0.1.8 

func (e *Edge) NeigborEdges(maxdist int) []*Edge

Returns the neighbors of the given edge.

The neighbors are defined by the branches located in a area defined by number of branches separating them (<d).

func (*Edge) NumTipsLeft added in v0.2.3 

func (e *Edge) NumTipsLeft() int

Number of tips on the left side of the bipartition Used by "TopoDepth" function for example.

Must be initialized with ComputeEdgeHashes.

func (*Edge) NumTipsRight added in v0.2.3 

func (e *Edge) NumTipsRight() int

Number of tips on the right side of the bipartition Used by "TopoDepth" function for example.

Must Be initialized with ComputeEdgeHashes.

func (*Edge) PValue added in v0.1.4 

func (e *Edge) PValue() float64

Returns the Pvalue of that branch

func (*Edge) Right 

func (e *Edge) Right() *Node

Returns the node at the right side of the edge (child)

func (*Edge) SameBipartition 

func (e *Edge) SameBipartition(e2 *Edge) bool

Returns true if this edge defines the same biparition of the tips than the edge in argument.

Bitsets must be initialized

func (*Edge) SetId 

func (e *Edge) SetId(id int)

Sets the id of the branch

func (*Edge) SetLength 

func (e *Edge) SetLength(length float64)

Sets the length of the branch

func (*Edge) SetPValue added in v0.1.4 

func (e *Edge) SetPValue(pval float64)

Sets the pvalue of this edge (if not null, pvalue is stored/parsed as "/pvalue" in the bootstrap value field.

func (*Edge) SetSupport 

func (e *Edge) SetSupport(support float64)

Sets the branch support

func (*Edge) Support 

func (e *Edge) Support() float64

Returns the support of that branch

func (*Edge) SupportString added in v0.2.1 

func (e *Edge) SupportString() string

Returns the support as a string representing the right precision float (not 0.90000000 but 0.9 for example)

func (*Edge) TipPresent 

func (e *Edge) TipPresent(id uint) bool

Tests wether the tip with index id in the bitset is Set or not.

The index corresponds to tree.Tipindex(tipname)

func (*Edge) ToStatsString added in v0.1.3 

func (e *Edge) ToStatsString(withedgecomments bool) string
Returns a string containing informations about the edge:

Tab delimited: 

	1 - length
	2 - support
	3 - istip?
	4 - depth
	5 - topo depth
	6 - name of right node if any
        7 - comments associated to the edge
        8 - name of left node if any
        9 - comment of right node if any
       10 - comment of left node if any

func (*Edge) TopoDepth 

func (e *Edge) TopoDepth() (int, error)

Returns the size (number of tips) of the light side (smallest number of tips) of the given branch.

Bitsets must be initialized otherwise returns an error.

type EdgeIndex 

type EdgeIndex struct {
	// contains filtered or unexported fields
}

Structure for an EdgeIndex. It is basically an HashMap, storing as key the bitset of the edge, and as value, the number of occurences of this edge already stored and the average branch lengths.

func NewEdgeIndex 

func NewEdgeIndex(size uint64, loadfactor float64) *EdgeIndex

Initializes an Edge Count Index

func (*EdgeIndex) AddEdgeCount 

func (em *EdgeIndex) AddEdgeCount(e *Edge) error

Increments edge count for an edge if it already exists in the map. If it does not exist, adds it with count 1

Also adds edge length

func (*EdgeIndex) Edges added in v0.4.0 

func (em *EdgeIndex) Edges(minCount, maxCount int) []*KeyValue

Returns all the Bipartitions of the index (bitset) with their counts included in ]min,max]. If min==Max==1 : [1].

Keys of the index

func (*EdgeIndex) PutEdgeValue 

func (em *EdgeIndex) PutEdgeValue(e *Edge, count int, length float64) error

Adds the edge in the map, with given value. If the edge already exists in the index The old value is erased

func (*EdgeIndex) Value 

func (em *EdgeIndex) Value(e *Edge) (*EdgeIndexInfo, bool)

Returns the count for the given Edge

  • If the edge is not present, returns 0 and false
  • If the edge is present, returns the value and true

type EdgeIndexInfo added in v0.1.2 

type EdgeIndexInfo struct {
	Count int     // Number of occurences of the branch
	Len   float64 // Mean length of branches occurences
}

Value stored in the HashMap

type KeyValue 

type KeyValue struct {
	// contains filtered or unexported fields
}

KeyValue Pair stored in the HashMap

type NNIRearranger added in v0.4.0 

type NNIRearranger struct {
}

func (*NNIRearranger) Rearrange added in v0.4.0 

func (nnir *NNIRearranger) Rearrange(t *Tree, f func(r Rearrangement) bool)

type Node 

type Node struct {
	// contains filtered or unexported fields
}

Node structure

func (*Node) AddComment 

func (n *Node) AddComment(comment string)

Adds a comment to the node. It will be coded by a list of [] In the Newick format.

func (*Node) ClearComments added in v0.2.3 

func (n *Node) ClearComments()

Removes all comments associated to the node

func (*Node) Comments added in v0.2.2 

func (n *Node) Comments() []string

Returns the list of comments associated to the node.

func (*Node) CommentsString added in v0.2.3 

func (n *Node) CommentsString() string

Returns the string of comma separated comments surounded by [].

func (*Node) Depth 

func (n *Node) Depth() (int, error)

Returns the depth of the node. Returns an error if the depth has not been set yet.

func (*Node) EdgeIndex 

func (n *Node) EdgeIndex(e *Edge) (int, error)

Returns the index of the given edge in the list of edges going from this node.

If the edge is not connected to the node n, then returns an error.

func (*Node) Edges 

func (n *Node) Edges() []*Edge

List of edges going from this node

func (*Node) Id added in v0.1.4 

func (n *Node) Id() int

Returns the Id of the node. Id==NIL_ID means that it has not been set yet.

func (*Node) IsConnected added in v0.4.0 

func (n *Node) IsConnected(next *Node) bool

Returns if a node "next" is connected to "n" in the tree

func (*Node) Name 

func (n *Node) Name() string

Returns the name of the node

func (*Node) Neigh 

func (n *Node) Neigh() []*Node

List of neighbors of this node

func (*Node) Newick 

func (n *Node) Newick(parent *Node, newick *bytes.Buffer)

Recursive function that outputs newick representation from the current node

func (*Node) Nneigh 

func (n *Node) Nneigh() int

Number of neighbors of this node

func (*Node) NodeIndex 

func (n *Node) NodeIndex(next *Node) (int, error)

Returns the index of the given node next in the list of neighbors of node n.

If next is not a neighbor of n, then returns an error.

func (*Node) Parent 

func (n *Node) Parent() (*Node, error)

Retrieve the parent node

If several parents: Error (should not happen). If no parent: Error (it is the root?)

Parent is defined as the node n2 connected to n by an edge e with e.left == n2 and e.right == n

func (*Node) ParentEdge 

func (n *Node) ParentEdge() (*Edge, error)

Retrieves the Edge going from node n to its parent node.

If several parents: Error (should not happen). If no parent: Error (it is the root?)

Parent is defined as the node n2 connected to n by an edge e with e.left == n2 and e.right == n

func (*Node) RotateNeighbors added in v0.2.10 

func (n *Node) RotateNeighbors()

Randomly rotates order of neighbor nodes and edges of a given node.

Topology is not changed, just the order of the tree traversal

func (*Node) SetDepth 

func (n *Node) SetDepth(depth int)

Sets the depth of the node

func (*Node) SetId added in v0.1.4 

func (n *Node) SetId(id int)

Sets the id of the node

func (*Node) SetName 

func (n *Node) SetName(name string)

Sets the name of the node. No verification if another node has the same name

func (*Node) Tip 

func (n *Node) Tip() bool

Is a tip or not?

func (*Node) TipIndex added in v0.4.0 

func (n *Node) TipIndex() int

Returns the Tip Id of the node. TipId==NIL_TIPIDINDEX means that it is not a tip or tipindex has not been initialized (use ReinitIndexes)

type NodeIndex 

type NodeIndex interface {
	GetNode(name string) (*Node, bool)
	AddNode(n *Node)
}

Structure of a node index. Basically a hashmap that stores as keys node names, and values node of the trees.

type Quartet added in v0.1.4 

type Quartet struct {
	/** Indexes of the taxa in the node index
	  t1       t3
	   \       /
	     -----
	   /       \
	  t2       t4
	*/
	T1, T2, T3, T4 uint
}

* Structure representing a "quartets"

func (*Quartet) Compare added in v0.1.4 

func (q *Quartet) Compare(q2 *Quartet) int
Compares the first quartet

(q1,q2)(q3,q4) With the second quartet (q5,q6)(q7,q8)

Returns:

  • QUARTET_EQUALS if they have the same taxa and the same topology
  • QUARTET_CONFLICT if they have the same taxa and different topology
  • QUARTET_DIFF if they have different taxa

func (*Quartet) HashCode added in v0.1.4 

func (q *Quartet) HashCode() uint64

* Quartets are hashed according to their unorder taxon index, i.e: (1,2)(3,4) == (1,3)(4,8) => because we do not want conflicting quartets 

in the map

func (*Quartet) HashEquals added in v0.1.4 

func (q *Quartet) HashEquals(h hashmap.Hasher) bool

* Equals returns true if quartets are equals or conflicting => for hashing

type QuartetSet added in v0.1.4 

type QuartetSet struct {
	// contains filtered or unexported fields
}

* Structure representing a "quartets set" Actually X sets of taxa defined by a bipartition (Maybe multifurcated) The enumeration of all the quartets is done by the "Quartets" function

func NewQuartetSet added in v0.1.4 

func NewQuartetSet() *QuartetSet

* Initializes a new empty quartet with 4 sets of taxa

type Rearrangement added in v0.4.0 

type Rearrangement interface {
	Apply() error
	Undo() error
}

Particular rearrangement (NNI, SPR, etc.)

type Rearranger added in v0.4.0 

type Rearranger interface {
	// List all rearragements
	Rearrange(t *Tree, f func(r Rearrangement) bool)
}

rearranger provides functions to modify input tree in order to search tree space

type TipBag added in v0.3.0 

type TipBag struct {
	// contains filtered or unexported fields
}

A bag of tips

func NewTipBag added in v0.3.0 

func NewTipBag() *TipBag

Initialize a new TipBag

func (*TipBag) AddTip added in v0.3.0 

func (tb *TipBag) AddTip(t *Node) error

Add a tip to the bag

  • If the same tip is already present: do nothing
  • If another tip of the tree with the same name is already present: returns an error. it means that the tree contains several tips that have the same name
  • If t is nil or if t is not a tip: returns an error

func (*TipBag) Clear added in v0.3.0 

func (tb *TipBag) Clear()

Removes all tips of the given TipBag

func (*TipBag) Size added in v0.3.0 

func (tb *TipBag) Size() int

Size of the TipBag in number of contained tips

func (*TipBag) Tips added in v0.3.0 

func (tb *TipBag) Tips() []*Node

List of tips in the bag Always returns tip in the same order (alphanumeric by tip name)

type Tree 

type Tree struct {
	// contains filtered or unexported fields
}

Tree structure having a root and a tip index, that maps tip names to their index

func AllTopologies added in v0.2.11 

func AllTopologies(nbTips int, rooted bool, tipNames ...string) (trees []*Tree, err error)

generate all possible topologies with nb tips rooted or not

func BipartitionTree added in v0.2.1 

func BipartitionTree(leftTips []string, rightTips []string) (*Tree, error)

Builds a single edge tree, given left taxa and right taxa 

\     /
-*---*-
/     \

Returns an error if size of lefTips is <=1 or size of rightTips w<= 1, or if tip names are common between left and right tip sets.

func Consensus added in v0.1.2 

func Consensus(trees <-chan Trees, cutoff float64) (*Tree, error)

Builds the consensus of trees given in the input channel.

  • If the cutoff is 0.5 : The majority rule consensus is computed;
  • If tht cutoff is 1 : The strict consensus is computed

In the output consensus tree:

  1. Branch supports are computed as the proportion of trees in which the bipartitions are present
  2. Branch lengths are computed as the average length of the same branch over all the trees where it is present

There can be errors if:

  • The cutoff <0.5 or >1
  • The tip names are different in the different trees
  • Incompatible bipartition are generated to build the consensus (It should not happen since cutoff should be >=0.5)

func EdgeTree added in v0.1.4 

func EdgeTree(t *Tree, e *Edge, alltips []string) *Tree

Builds a tree whose only internal edge is the given edge e The two internal nodes are multifurcated 

\     /
-*---*-
/     \

alltips is the slice containing all tip names of the tree. if it is nil, it will be recomputed from the given tree.

func NewTree 

func NewTree() *Tree

Initialize a new empty Tree

func RandomBalancedBinaryTree added in v0.1.6 

func RandomBalancedBinaryTree(depth int, rooted bool) (*Tree, error)

Creates a Random Balanced Binary tree. Does it recursively until the given depth is attained. Root is at depth 0. So a depth "d" will generate a tree with 2^(d) tips.

  • depth : Depth of the balanced binary tree
  • rooted: if true, generates a rooted tree
  • branch length: follow an exponential distribution with param lambda=1/0.1

func RandomCaterpillarBinaryTree added in v0.2.3 

func RandomCaterpillarBinaryTree(nbtips int, rooted bool) (*Tree, error)

Creates a Random Caterpillar tree by adding new tips to the last added terminal edge of the tree.

  • nbtips : Number of tips of the random binary tree to create
  • rooted: if true, generates a rooted tree
  • branch length: follows an exponential distribution with param lambda=1/0.1

func RandomUniformBinaryTree added in v0.1.5 

func RandomUniformBinaryTree(nbtips int, rooted bool) (*Tree, error)

Creates a Random uniform Binary tree by successively adding new tips to a random edge of the tree.

  • nbtips : Number of tips of the random binary tree to create
  • rooted: if true, generates a rooted tree
  • branch length: follow an exponential distribution with param lambda=1/0.1

func RandomYuleBinaryTree added in v0.1.5 

func RandomYuleBinaryTree(nbtips int, rooted bool) (*Tree, error)

Creates a Random Yule tree by successively adding new tips to random terminal edges of the tree.

  • nbtips : Number of tips of the random binary tree to create
  • rooted: if true, generates a rooted tree (actually if false, unroots the given tree)
  • branch lengths: follow an exponential distribution with param lambda=1/0.1

func StarTree added in v0.1.2 

func StarTree(nbtips int) (*Tree, error)

Creates a Star tree with nbtips tips.

Since there is only one possible labelled tree, no need of randomness.

  • nbtips : Number of tips of the star tree.
  • Branch lengths are all set to 1.0

func StarTreeFromName added in v0.1.2 

func StarTreeFromName(names ...string) (*Tree, error)

Creates a star tree using tipnames in argument Since there is only one possible labelled tree, no need of randomness.

Branch lengths are all set to 1.0

func StarTreeFromTree added in v0.1.2 

func StarTreeFromTree(t *Tree) (*Tree, error)

Creates a Star tree with the same tips as the tree in argument Lengths of branches in the star trees are the same as lengths of terminal edges of the input tree

func (*Tree) AddBipartition added in v0.1.2 

func (t *Tree) AddBipartition(n *Node, edges []*Edge, length, support float64) (*Edge, error)

This function adds a branch/bipartition between the given node n and the given edges. To do so, it creates a new node between n and the edges, and connects it with a new edge.

Imagine a star tree with central node n, 

     1
     |
     |
6----n-----2
    /|\
   / | \
 e5 e4  e3

if we call AddBipartition(n,{e3,e4,e5}), at the end we have: 

     1
     |
     |
6----n-----2
     |
     |
     n2
    /|\
   / | \
 e5 e4  e3

Useful for building consensus tree.

If the edges are not initially directly connected to n, then returns an error. If ony one edge is given, returns an error (no need to add a new edge).

func (*Tree) AllTipNames 

func (t *Tree) AllTipNames() []string

Returns all the tip name in the tree Starts with n==nil (root)

func (*Tree) Annotate added in v0.1.9 

func (t *Tree) Annotate(names [][]string, comment bool) error

Annotates internal branches of a tree with given data using the given list of names:

  • each element is a slice of names whose first element is the new name to set
  • following names are internal node name or tip names defining an internal node (LCA)

For a given element different possibilities:

  1. If < 2 names: an error is returned
  2. If 2 names [n1,n2]: we search for n2 in the tree (tip or internal node) and rename it as n1
  3. If > 2 names [n1,n2,...,ni]: We find the LCA of every tips whose name is in [n2,...,ni] and rename it as n1

If comment is true, then we do not change the name, but the comment of the given nodes.

The output tree won't have bootstrap support at the given branches anymore.

It considers the tree as rooted (even if multifurcation at root).

func (*Tree) CheckTree added in v0.3.1 

func (t *Tree) CheckTree() bool

Check that tree is well structured, with the right child, parent, edges, and node pointers

func (*Tree) CheckTreePostOrder added in v0.4.0 

func (t *Tree) CheckTreePostOrder() (err error)

Checks that edges are proerly oriented And that edges connect proper nodes For testing purpose

func (*Tree) ClearBitSets 

func (t *Tree) ClearBitSets() error

Clears all bitsets associated to all edges

func (*Tree) ClearComments added in v0.2.3 

func (t *Tree) ClearComments()

Clears comments associated to all nodes, tips and edges of the tree

func (*Tree) ClearEdgeComments added in v0.2.7 

func (t *Tree) ClearEdgeComments()

func (*Tree) ClearLengths added in v0.1.5 

func (t *Tree) ClearLengths()

Clears length (set to NIL_LENGTH) of all branches of the tree

func (*Tree) ClearNodeComments added in v0.2.7 

func (t *Tree) ClearNodeComments()

func (*Tree) ClearPvalues added in v0.1.8 

func (t *Tree) ClearPvalues()

Clears pvalues associated with supports (set to NIL_PVALUE) of all branches of the tree

func (*Tree) ClearSupports added in v0.1.5 

func (t *Tree) ClearSupports()

Clears support (set to NIL_SUPPORT) of all branches of the tree

func (*Tree) Clone added in v0.1.5 

func (t *Tree) Clone() *Tree

Clone the input tree

func (*Tree) CollapseLowSupport added in v0.1.5 

func (t *Tree) CollapseLowSupport(support float64)

Collapses (removes) the branches having support < support threshold && support != NIL_SUPPORT (exists)

func (*Tree) CollapseShortBranches 

func (t *Tree) CollapseShortBranches(length float64)

Collapses (removes) the branches having length <= length threshold

func (*Tree) CollapseTopoDepth added in v0.1.9 

func (t *Tree) CollapseTopoDepth(mindepthThreshold, maxdepthThreshold int) error

Collapses (removes) the branches having their depth d (# taxa on the lightest side of the bipartition) such that mindepththreshold<=d<=maxdepththreshold

func (*Tree) CollessIndex added in v0.2.3 

func (t *Tree) CollessIndex() (colless int)

Returns the colless index of the tree.

It computes the colless index of a rooted tree as the Sum over nodes v of |S(left(V))-S(right(V))|. With Sleft(V)=Size of the left sublcade of V and Sright(V)=size of the right subclade of V.

If the tree is unrooted, then it takes as starting point the deepest edge of the tree (not the classical definition of Colless index which is computed only for rooted trees).

If there are multifurcations, then the index of node V will be (Smax(V)-Smin(V)), with Smax(V)=Size of the largest subclade of V and Smin(V) size the smallest subclade of V (not the classical definition of Colless index which is computed only for binary trees).

func (*Tree) CommonEdges 

func (t *Tree) CommonEdges(t2 *Tree, tipEdges bool) (tree1 int, common int, err error)

This function compares 2 trees and returns the number of edges in common If the trees have different sets of tip names, returns an error.

It assumes that functions 

tree.UpdateTipIndex()
tree.ClearBitSets()
tree.UpdateBitSet()

Have been called before, otherwise will output an error

If tipedges is false: does not take into account tip edges

func (*Tree) CompareTipIndexes 

func (t *Tree) CompareTipIndexes(t2 *Tree) error

This function compares the tip name indexes of 2 trees

If the tipindexes have the same size (!=0) and have the same set of tip names, then returns nil, otherwise returns an error

func (*Tree) ComputeDepths 

func (t *Tree) ComputeDepths()

Computes detphs of all nodes. Depth of internal node n is defined as the length of the path from n to the closest tip. Depth of tip nodes is 0.

Depth is then accessible by n.Depth() for any node n.

func (*Tree) ComputeEdgeHashes added in v0.4.0 

func (t *Tree) ComputeEdgeHashes(cur, prev *Node, e *Edge)

func (*Tree) ConnectNodes 

func (t *Tree) ConnectNodes(parent *Node, child *Node) *Edge

Connects the two nodes in argument by an edge that is returned.

func (*Tree) CopyEdge added in v0.1.5 

func (t *Tree) CopyEdge(e *Edge, copy *Edge)

Copy attributes of the given edge to the other given edge:

  • Length
  • Support
  • id
  • bitset (if not nil)

func (*Tree) CopyNode added in v0.1.5 

func (t *Tree) CopyNode(n *Node) *Node

Clone the given node, copy attributes of the given node into a new node

func (*Tree) CutEdgesMaxLength added in v0.3.0 

func (t *Tree) CutEdgesMaxLength(maxlen float64) (bags []*TipBag, err error)

Get all connected components (only the tips) of the tree when edges with length less than maxLen (included) are removed If a connected components have no tips, then it is not taken into account.

The edges are not actually removed from the input tree.

func (*Tree) DeepestEdge added in v0.2.3 

func (t *Tree) DeepestEdge() (maxedge *Edge)

Returns the deepest edge of the tree (considered unrooted) in terms of number of tips on the light side of it.

It does not use bitsets, thus they may be uninitialized.

func (*Tree) DeepestNode added in v0.2.4 

func (t *Tree) DeepestNode() (maxnode *Node)

Returns the deepest node of the tree (considered unrooted).

We define the deepest node as the heavy side of the deepest edge (See tree.DeepestEdge())

It does not use bitsets, thus they may be uninitialized.

func (*Tree) Delete added in v0.2.9 

func (t *Tree) Delete()

func (*Tree) Edges 

func (t *Tree) Edges() []*Edge

Returns all the edges of the tree (do it recursively)

func (*Tree) ExistsTip 

func (t *Tree) ExistsTip(name string) (bool, error)

Return true if the tip with given name exists in the tree May return an error if tip index has not been initialized With UpdateTipIndex

func (*Tree) GraftTipOnEdge 

func (t *Tree) GraftTipOnEdge(n *Node, e *Edge) (*Edge, *Edge, *Node, error)

This function grafts the Tip n at the middle of the Edge e.

Example:

  • Before *--e--*
  • After *--e1--newnode--e2--* | n

To do so, it divides the branch lenght by 2,and returns the 2 new edges and the new internal node.

func (*Tree) IndexQuartets added in v0.1.4 

func (t *Tree) IndexQuartets(specific bool) *hashmap.HashMap

func (*Tree) InsertIdenticalTip added in v0.3.1 

func (t *Tree) InsertIdenticalTip(n *Node, newTipName string) (newtipnode *Node, err error)

This function adds a new tip next to the given tip node. This adds two 0 length branches. The given node reference is still a tip after this function. The new node is the internal node.

Before: 

l

*----*tip1 After: 

     *tip1
l   /.0

----* 

\.0
 *newTipName

If l==0.0 then, after: 

 *tip1
/.0

* 

\.0
 *newTipName

Warning: This function may add polytomies if l==0.0.

It updates the tipindex temporarily but if needed in downstream analysis t.ReinitIndexes() must be called. If initialized, Bitsets and Depths are not up2date after this function. They should be updated with t.ReinitIndexes() if needed.

func (*Tree) InsertIdenticalTips added in v0.3.1 

func (t *Tree) InsertIdenticalTips(identicalgroups [][]string) (err error)

This function adds Tips to the tree, adding 0 length branches. To do so, it takes all identical tipnames of the given slice And add the new tip names next to the existing ones, by adding 0 length branches. Each identical group must contain exactly 1 already present tip otherwise returns an error If a new tip is identical to several already present tips, then returns and error.

func (*Tree) InternalEdges added in v0.1.13 

func (t *Tree) InternalEdges() []*Edge

Returns all internal edges of the tree (do it recursively)

func (*Tree) LeastCommonAncestorRecur added in v0.2.1 

func (t *Tree) LeastCommonAncestorRecur(current *Node, prev *Node, tipIndex map[string]*Node) (*Node, []*Edge, int, int, bool, error)

recursive function for getting the least common ancestor.

func (*Tree) LeastCommonAncestorRooted added in v0.2.1 

func (t *Tree) LeastCommonAncestorRooted(nodeindex *nodeIndex, tips ...string) (*Node, []*Edge, bool, error)

Given a set of tip names, this function returns the node that is the common ancestor of them and the edges that connect this LCA node to the subtree.

It considers the tree as Rooted.

The returned boolean value tell if the group is monophyletic or not (i.e. contains all tips descending from LCA).

func (*Tree) LeastCommonAncestorUnrooted added in v0.1.2 

func (t *Tree) LeastCommonAncestorUnrooted(nodeindex *nodeIndex, tips ...string) (*Node, []*Edge, bool, error)

Given a set of tip names, this function returns the node that is the common ancestor of them and the edges that connects this node to the subtree.

It considers the tree as unrooted 

       e2---1
 ----a|
|      e1---2
|     ---3
 ----|
|     ---4
|     ---5
 ----|
      ---6

LeastCommonAncestorUnrooted(1,2) returns a,e1,e2,true

The returned boolean value telling if the group is monophyletic (i.e. contains all tips descending from LCA).

func (*Tree) MeanBranchLength added in v0.2.3 

func (t *Tree) MeanBranchLength() float64

Returns the average branch lengths

func (*Tree) MeanSupport 

func (t *Tree) MeanSupport() float64

Returns the average branch support

func (*Tree) MedianSupport 

func (t *Tree) MedianSupport() float64

Returns the median branch support

func (*Tree) Merge added in v0.2.3 

func (t *Tree) Merge(t2 *Tree) error

Merges Two rooted trees t and t2 in t by adding a new root node with two children Corresponding to the roots of the 2 trees.

If one of the tree is not rooted, returns an error.

Tip set must be different between the two trees, otherwise returns an error.

it is advised not to use t2 after the merge, since it may conflict with t.

Edges connecting the new root with old roots have length of 1.0, but can be modified afterwards.

func (*Tree) NbCherries added in v0.2.3 

func (t *Tree) NbCherries() (nbcherries int)

Returns the number of cherries in the tree

func (*Tree) NbTips 

func (t *Tree) NbTips() (int, error)

Returns the number if tips of the tree

If UpdateTipIndex has been called before ok otherwise returns an error

func (*Tree) NewEdge 

func (t *Tree) NewEdge() *Edge

Initialize a new empty Edge

func (*Tree) NewNode 

func (t *Tree) NewNode() *Node

Initialize a new empty Node

func (*Tree) Newick 

func (t *Tree) Newick() string

Returns a newick string representation of this tree

func (*Tree) Nexus added in v0.2.3 

func (t *Tree) Nexus() string

returns a Nexus string representation of this tree

func (*Tree) Nodes 

func (t *Tree) Nodes() []*Node

Returns all the nodes of the tree (do it recursively)

func (*Tree) PostOrder added in v0.3.0 

func (t *Tree) PostOrder(f func(cur *Node, prev *Node, e *Edge) (keep bool))

func (*Tree) PreOrder added in v0.3.0 

func (t *Tree) PreOrder(f func(cur *Node, prev *Node, e *Edge) (keep bool))

func (*Tree) Quartets added in v0.1.4 

func (t *Tree) Quartets(specific bool, it func(q *Quartet))

* Iterate over all the quartets of the tree, edge by edge (t1,t2)(t3,t4) specific: If true gives the specific quartets 

 b0       b2
  \       /
left-----right
  /       \
 b1       b3

Else gives all the quartets 

            b0-|\       /|-b2
	       | >-----< |
            b1-|/       \|-b3

func (*Tree) ReinitIndexes added in v0.2.2 

func (t *Tree) ReinitIndexes() (err error)

This Function initializes or reinitializes memory consuming structures:

  • bitset indexes
  • Tipindex
  • And computes node depths

func (*Tree) ReinitInternalIndexes added in v0.4.0 

func (t *Tree) ReinitInternalIndexes()

This Function initializes or reinitializes memory consuming structures:

  • bitset indexes
  • Tipindex
  • And computes node depths

func (*Tree) RemoveEdges 

func (t *Tree) RemoveEdges(edges ...*Edge)

Removes the given branches from the tree if they are not tip edges and if they do not connect to the root of a rooted tree.

Merges the 2 nodes and creates multifurcations.

At the end, bitsets should not need to be updated

func (*Tree) RemoveSingleNodes added in v0.2.2 

func (t *Tree) RemoveSingleNodes()

Removes Edges for which the left node has a unique child:

Example: 

          t1           t1
          /	       /
n0--n1--n2   => n0--n2
          \	       \
           t2          t2

Will remove edge n1-n2 and keep node n2 informations (name, etc.) It adds n1-n2 length to n0-n1 (if any) and keeps n0-n1 support (if any) Useful for cleaning ncbi taxonomy for example.

func (*Tree) RemoveTips 

func (t *Tree) RemoveTips(revert bool, names ...string) error

Removes a set of tips from the tree, given their names

if revert is true, then keeps only tips with the given names

Removed tips

func (*Tree) Rename 

func (t *Tree) Rename(namemap map[string]string) error

This function renames nodes of the tree based on the map in argument If a name in the map does not exist in the tree, then returns an error If a node/tip in the tree does not have a name in the map: OK After rename, tip index is updated, as well as bitsets of the edges

func (*Tree) RenameAuto added in v0.2.11 

func (t *Tree) RenameAuto(internals, tips bool, length int, curid *int, namemap map[string]string) error

Renames automatically nodes/tips of the Tree, with names of the form T000001, N00001, etc.

internals: Renames internal nodes tips: Renames tips length: length of the generated names curid: index that is incremented, to keep track of the number of generated names namemap: map that associates old names to new names - allows to keep track of renames for previous trees

func (*Tree) RenameRegexp added in v0.2.11 

func (t *Tree) RenameRegexp(internals, tips bool, regex, replace string, namemap map[string]string) error

Renames nodes/tips of the Tree, given the regexp and a replaement string

internals: Renames internal nodes tips: Renames tips regexp: the regexp to match node names replace: Replacement string namemap: map that associates old names to new names

func (*Tree) ReorderEdges added in v0.2.3 

func (t *Tree) ReorderEdges(n *Node, prev *Node, reversed *[]*Edge) error

This function reorders the edges of a tree in order to always have left-edge-right with left node being parent of right node with respect to the given root node.

Important even for unrooted trees. Useful mainly after a reroot.

It updates "reversed" edge slice, edges that have been reversed

func (*Tree) Reroot 

func (t *Tree) Reroot(n *Node) error

This function takes a node and reroots the tree on that node.

It reorients edges left-edge-right : see ReorderEdges()

The node must be part of the tree, otherwise it returns an error

func (*Tree) RerootFirst 

func (t *Tree) RerootFirst() error

This function takes the first node having 3 neighbors and reroot the tree on this node It then recomputes indices

func (*Tree) RerootMidPoint added in v0.1.6 

func (t *Tree) RerootMidPoint() error

This function reroots the tree at the midpoint position. To do so, it first gets the 2 farthest tips of the tree, and takes the middle of the path between these tips as the new root position.

func (*Tree) RerootOutGroup added in v0.1.5 

func (t *Tree) RerootOutGroup(removeoutgroup, strict bool, tips ...string) error

This function first unroots the input tree and reroots it using the outgroup in argument.

If the outgroup is not monophyletic and strict is false, it will take all the descendant of the LCA and print a warning. If strict is true, it returns an error.

An error is returned if the LCA is multifurcated, and several branches are possible for the placement of the root.

If the outgroup includes a tip that is not present in the tree, this tip will not be taken into account for the rerooting.

If removeoutgroup is true, then the outgrouped is removed from the rerooted tree.

func (*Tree) Resolve added in v0.1.9 

func (t *Tree) Resolve()

Resolves multifurcating nodes (>3 neighbors).

If any node has more than 3 neighbors, then neighbors are resolved randomly by adding 0 length branches until 3 neighbors are remaining.

This function does not update bitsets on edges.

If needed, the calling function must do it with: 

err := t.ClearBitSets()
if err != nil {
	return err
}
t.UpdateBitSet()

func (*Tree) Root 

func (t *Tree) Root() *Node

Returns the current root of the tree

func (*Tree) Rooted 

func (t *Tree) Rooted() bool

Returns true if the tree is rooted (i.e. root node has 2 neighbors), and false otherwise.

func (*Tree) RotateInternalNodes added in v0.2.10 

func (t *Tree) RotateInternalNodes()

Randomly rotates neighbors of all internal nodes

It does not change the topology, but just the way the tree is traversed.

func (*Tree) RoundLengths added in v0.2.11 

func (t *Tree) RoundLengths(precision int)

Rounds branch lengths by a given precision. Precision is defined as 1/(power of 10) Example: 6, means 10^-6.

Does not do anything for branches with a length of NIL_LENGTH or if precision is <=0. If precision > 15, then 15 is taken

func (*Tree) RoundSupports added in v0.2.11 

func (t *Tree) RoundSupports(precision int)

Rounds branch supports by a given precision. Precision is defined as 1/(power of 10) Example: 6, means 10^-6

Does not do anything for branches with a support of NIL_SUPPORT or if precision is <=0 If precision > 15, then 15 is taken

func (*Tree) SackinIndex added in v0.2.3 

func (t *Tree) SackinIndex() (sackin int)

Computes the Sackin index of the tree

This functions computes the Sackin index of a rooted tree as the sum of all tip depths.

If the tree is unrooted, then it takes as starting point the deepest edge of the tree (not the classical definition of Sackin index which is computed only for rooted trees).

No problems with multifurcations.

func (*Tree) ScaleLengths added in v0.2.5 

func (t *Tree) ScaleLengths(factor float64)

Scale branch lengths by a given factor.

Does not do anything for branches with a length of NIL_LENGTH

func (*Tree) ScaleSupports added in v0.2.5 

func (t *Tree) ScaleSupports(factor float64)

Scale branch supports by a given factor. Precision 10^-6.

Does not do anything for branches with a support of NIL_SUPPORT

func (*Tree) SelectNodes added in v0.2.0 

func (t *Tree) SelectNodes(re string) ([]*Node, error)

Returns the list of nodes having a name matching the given regexp May return an error if the regexp is malformed. In this case, returns an empty (not nil) slice of nodes.

func (*Tree) SetRoot 

func (t *Tree) SetRoot(r *Node)

Set a root for the tree. This does not check that the node is part of the tree. It may be useful to call 

t.ReinitIndexes()

After setting a new root, to update branch bitsets.

func (*Tree) ShuffleTips 

func (t *Tree) ShuffleTips()

This function shuffles the tips of the tree and recompute tipindex and bitsets.

The tree have the same topology, but tip names are reassigned randomly.

func (*Tree) SortNeighborsByTips added in v0.2.10 

func (t *Tree) SortNeighborsByTips()

Sort neighbors of all nodes by their number of tips

May give better results for drawing.

func (*Tree) SortedTips added in v0.1.13 

func (t *Tree) SortedTips() []*Node

Tips, sorted by their order in the bitsets

func (*Tree) String 

func (t *Tree) String() string

Returns a newick string representation of this tree It calls t.Newick()

func (*Tree) SubTree added in v0.2.0 

func (t *Tree) SubTree(n *Node) *Tree

Assumes that the tree is rooted.

Otherwise, will consider the pseudo root defined by the initial newick file

func (*Tree) SumBranchLengths 

func (t *Tree) SumBranchLengths() float64

Returns the sum of branch lengths

func (*Tree) TipEdges 

func (t *Tree) TipEdges() []*Edge

Returns all the external edges (tip) of the tree (do it recursively)

func (*Tree) TipIndex 

func (t *Tree) TipIndex(name string) (int, error)

Return the tip index if the tip with given name exists in the tree May return an error if tip index has not been initialized With UpdateTipIndex or if the tip does not exist

func (*Tree) TipNode added in v0.4.0 

func (t *Tree) TipNode(name string) (tip *Node, err error)

Return the tip Node if the tip with given name exists in the tree May return an error if tip index has not been initialized With UpdateTipIndex or if the tip does not exist

func (*Tree) Tips 

func (t *Tree) Tips() []*Node

Returns all the tips of the tree (do it recursively)

func (*Tree) ToDistanceMatrix added in v0.1.7 

func (t *Tree) ToDistanceMatrix() [][]float64

This function computes and returns the distance (sum of branch lengths) between all pairs of tips in the tree (patristic distance).

Computes patristic distance matrix.

func (*Tree) UnRoot 

func (t *Tree) UnRoot()

Unroots a rooted tree by removing the bifurcating root, and rerooting to one of the non tip direct children of the previous root.

func (*Tree) UpdateBitSet 

func (t *Tree) UpdateBitSet() error

Updates bitsets of all edges in the tree Assumes that the hashmap tip name : index is initialized with UpdateTipIndex function

func (*Tree) UpdateTipIndex 

func (t *Tree) UpdateTipIndex() (err error)

Updates the tipindex which maps tip names to their index in the bitsets.

Bitset indexes correspond to the position of the tip in the alphabetically ordered tip name list

type Trees added in v0.1.2 

type Trees struct {
	Tree *Tree
	Id   int
	Err  error
}

Type for channel of trees

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.