tree

package
v0.1.13 Latest Latest
Warning

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

 Go to latest Published: Mar 10, 2017 License: GPL-2.0 Imports: 11 Imported by: 0

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.0
)
View Source 
const (
	QUARTET_EQUALS = iota
	QUARTET_CONFLICT
	QUARTET_DIFF
)
View Source 
const (
	NIL_DEPTH = -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 output 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 applied on two tree with the same number of tips with different names, it will give results anyway It assumes that functions 

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

If tipedges is false: does not take into account tip edges Have been called before, otherwise will output an error

func NewNodeIndex 

func NewNodeIndex(t *Tree) *nodeIndex

Types

type Edge 

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

func MaxLengthPath added in v0.1.6 

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

Take 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

func (*Edge) Bitset 

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

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

func (*Edge) Id 

func (e *Edge) Id() int

func (*Edge) Left 

func (e *Edge) Left() *Node

func (*Edge) Length 

func (e *Edge) Length() float64

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 with length of the path separating the branches < 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) NeigborEdges added in v0.1.8 

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

Returns the neighbors of the given edge. Neighbors are defined as branches separated of given branch by a path whose length < maxdist

func (*Edge) NumTips 

func (e *Edge) NumTips() uint

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

func (*Edge) PValue added in v0.1.4 

func (e *Edge) PValue() float64

func (*Edge) Right 

func (e *Edge) Right() *Node

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

func (*Edge) SetId 

func (e *Edge) SetId(id int)

func (*Edge) SetLength 

func (e *Edge) SetLength(length float64)

func (*Edge) SetPValue added in v0.1.4 

func (e *Edge) SetPValue(pval float64)

func (*Edge) SetSupport 

func (e *Edge) SetSupport(support float64)

func (*Edge) Support 

func (e *Edge) Support() float64

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() 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 node if any

func (*Edge) TopoDepth 

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

Returns the size (number of tips) of the smallest subtree between the two subtrees connected to this edge

type EdgeIndex 

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

func NewEdgeIndex 

func NewEdgeIndex(size int64, loadfactor float64) *EdgeIndex

Initializes an Edge Count Index

func (*EdgeIndex) AddEdgeCount 

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

Increment edge count for an edge if it already exists in the map Otherwise adds it with count 1

func (*EdgeIndex) BitSets added in v0.1.2 

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

Returns all the Bipartitions of the index (bitset) with their counts That have a count 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)

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
}

type EdgeKey added in v0.1.4 

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

func (*EdgeKey) HashCode added in v0.1.4 

func (k *EdgeKey) HashCode() int64

HashCode for an Edge. Used for insertion in an HashMap

func (*EdgeKey) HashEquals added in v0.1.4 

func (k *EdgeKey) HashEquals(h hashmap.Hasher) bool

HashCode for an edge bitset. Used for insertion in an EdgeMap

type KeyValue 

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

type Node 

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

func (*Node) AddComment 

func (n *Node) AddComment(comment string)

func (*Node) Depth 

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

func (*Node) EdgeIndex 

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

func (*Node) Edges 

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

func (*Node) Id added in v0.1.4 

func (n *Node) Id() int

func (*Node) Name 

func (n *Node) Name() string

func (*Node) Neigh 

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

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)

func (*Node) Parent 

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

Retrieve the parent node If several parents: Error 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)

Retrieve the Edge going to Parent node If several parents: Error Parent is defined as the node n2 connected to n by an edge e with e.left == n2 and e.right == n

func (*Node) SetDepth 

func (n *Node) SetDepth(depth int)

func (*Node) SetId added in v0.1.4 

func (n *Node) SetId(id int)

func (*Node) SetName 

func (n *Node) SetName(name string)

func (*Node) Tip 

func (n *Node) Tip() bool

Is a tip or not?

type NodeIndex 

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

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() int64

* 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 Tree 

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

func Consensus added in v0.1.2 

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

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 bipartition is 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 nil, it will be recomputed

func NewTree 

func NewTree() *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 RandomCaterpilarBinaryTree added in v0.1.5 

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

Creates a Random Caterpilar 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: follow 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 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

This function adds a bipartition at the given node and the given edges Immagine a star tree with central node n, 

1
|
|

6----n-----2 

   /|\
  / | \
e5 e4  e3

if we call AddBipartition(n,{e3,e4,e5}) we end with: 

1
|
|

6----n-----2 

    |
    |
    n2
   /|\
  / | \
e5 e4  e3

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 map[string][]string)

Annotates internal branches of a tree with given data Takes a map with - key: name of internal branch - value: names of taxa => It will take the lca of taxa and annotate it => Output tree won't have bootstrap support at the branches anymore

func (*Tree) ClearBitSets 

func (t *Tree) ClearBitSets() error

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) 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)

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

func (*Tree) CommonEdges 

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

This function compares 2 trees and output 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()

If tipedges is false: does not take into account tip edges Have been called before, otherwise will output an error

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, The returns nil, otherwise returns an error

func (*Tree) ComputeDepths 

func (t *Tree) ComputeDepths()

func (*Tree) ConnectNodes 

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

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

func (*Tree) CopyNode added in v0.1.5 

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

Copy attributes of the node into a new node

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 graft the Node n at the middle of the Edge e It divides the branch lenght by 2 It returns the added edges and the added nodes

func (*Tree) IndexQuartets added in v0.1.4 

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

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) LeastCommonAncestorUnrooted added in v0.1.2 

func (t *Tree) LeastCommonAncestorUnrooted(nodeindex *nodeIndex, tips ...string) (*Node, []*Edge, bool)
Given a set of tip names

returns the node that is the common ancestor of them and the edges that connects this node to the subtree => Considers the tree as unrooted 

      e2---1
----a|

| e1---2 | ---3 

----|

| ---4 | ---5 

----|
     ---6

LeastCommonAncestorUnrooted(1,2) returns a,e1,e2,true returned boolean value is true if the group is monophyletic

func (*Tree) LeastCommonAncestorUnrootedRecur added in v0.1.2 

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

Returns for a given node ...

func (*Tree) MeanBrLength 

func (t *Tree) MeanBrLength() float64

func (*Tree) MeanSupport 

func (t *Tree) MeanSupport() float64

func (*Tree) MedianSupport 

func (t *Tree) MedianSupport() float64

func (*Tree) NbTips 

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

if UpdateTipIndex has been called before ok otherwise returns an error

func (*Tree) NewEdge 

func (t *Tree) NewEdge() *Edge

func (*Tree) NewNode 

func (t *Tree) NewNode() *Node

func (*Tree) Newick 

func (t *Tree) Newick() string

func (*Tree) Nodes 

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

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

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) RemoveEdges 

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

Removes branches from the tree if they are not tip edges And if they do not connects 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) RemoveTips 

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

Removes a set of tips from the tree, from tip names

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) Reroot 

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

This function takes a node and reroot the tree on that node It reorients edges left-edge-right : see ReorderEdges The node must be one of the tree nodes, 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

func (*Tree) RerootMidPoint added in v0.1.6 

func (t *Tree) RerootMidPoint()

func (*Tree) RerootOutGroup added in v0.1.5 

func (t *Tree) RerootOutGroup(tips ...string) error

This function first unroot the input tree and reroot it using the outgroup in argument if the outgroup is not monophyletic, it will take all the descendant of the LCA. An error is triggered 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 reroot.

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 : Resolve neighbors randomly by adding 0 length branches until it has 3 neighbors

func (*Tree) Root 

func (t *Tree) Root() *Node

func (*Tree) Rooted 

func (t *Tree) Rooted() bool

func (*Tree) SetRoot 

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

func (*Tree) ShuffleTips 

func (t *Tree) ShuffleTips()

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

func (*Tree) SortedTips added in v0.1.13 

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

Tips, sorted by their order in the bitsets

func (*Tree) String 

func (t *Tree) String() string

func (*Tree) SumBrLength added in v0.1.5 

func (t *Tree) SumBrLength() float64

func (*Tree) SumBranchLengths 

func (t *Tree) SumBranchLengths() float64

func (*Tree) TipEdges 

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

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

func (*Tree) TipIndex 

func (t *Tree) TipIndex(name string) (uint, 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) 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

Computes and returns the distance (sum of branch lengths) between all pairs of tips in the tree

func (*Tree) UnRoot 

func (t *Tree) UnRoot()

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()

Updates the tipindex which maps tip names To 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
}

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.