BACKGROUND
cell differentiation is the process by which a less specialized cell becomes a more specialized one; it often proceeds in a hierarchical manner, with totipotent cells sequentially committing to fates of more restricted developmental potential  <cit> .
epigenetic and transcription factors play a significant role in cell differentiation , therefore motivating a study of epigenetic changes across different cell types.
arendt  <cit>  proposed a sister-cell-type model for the hierarchical relationship between cell types.
in this model  <cit> , “novel cell types arise in pairs  from an ancestral cell type through sub-specialization”  <cit> .
under this model  <cit> , the evolutionary relatedness of cell types is expected to be congruent with the ontogenetic hierarchy of cellular differentiation, because the “development of the sister cell types is the same up to the last stages of differentiation”  <cit> .
the authors claim that multifunctionality has been a general feature of ancient cell types and that, with “increasing specialization during evolution, these multiple functions were then distributed in a complementary manner to sister cell types”  <cit> .
evolution and cell differentiation share a number of attributes.
first, as mentioned before, we know that cell differentiation transforms less specialized cell types into more specialized ones.
since this transformation is unidirectional, the paths of differentiation can be represented as a tree structure, much as is done with the phylogenetic trees used to represent evolutionary histories  <cit> .
the similarity between the two extends further: cell types themselves have evolved into larger collections from more restricted collections in early ancestors: there are phylogenetic relationships among the various types of cells.
second, observed changes in the epigenetic state are inheritable, again much as mutations in the genome are ; and finally, epigenetic traits are subject to stochastic changes.
one major difference between evolution and cell differentiation is that functional changes in cell differentiation are primarily driven by programmed mutational events rather than by selection.
however, the program of mutational events is itself the result of evolution, so that, as observed by  <cit> , the cell differentiation tree often recapitulates the phylogeny of cell types.
we focus here on one important epigenetic mark—histone modification.
histones are proteins that package the dna into nucleosomes  <cit> .
these proteins are subjected to various types of chemical modifications, called histone modifications, such as methylation, acetylation, phosphorylation, ubiquitination, etc.
these modifications alter their interactions with the dna and thereby influence transcription and genomic function.
histone modifications have been found to vary across cell types and to play an important role in gene regulation  <cit> .
since histones are present in every  <dig> bp length of dna, we need genome-wide high-throughput technologies to study the modifications of these proteins.
chip-seq is such a technology  <cit> .
the study of chip-seq histone modification data can help us understand the role of histone modifications in developmental biology and cell differentiation  <cit> .
the term “cell-type tree” was defined by our group to refer to a tree relationship between various cell types  <cit> .
the nodes of this tree represent cell types while the edges represent directed differentiation/evolution events from one cell type to another.
we know that the genome is consistent across cell types of the same individual and that it is also highly similar between individuals of the same species, but that epigenomic states of various regions of the genome differ across various cell types.
these epigenomic states are believed to affect cell differentiation process through a complex interplay between histone modifications, dna methylation, transcription factors, etc.
kin et al.
<cit>  recently constructed a cell-type tree using rna-seq data and a parsimony-based approach under assumptions very similar to ours, using the same term of “cell-type tree” to denote the “hypothetical tree-like relationship of cell types in ontogeny and phylogeny”.
liang et al.
<cit>  recently developed a statistical model for cell differentiation and applied it to encode and fantom rna-seq data.
as in kin et al.
work  <cit> , they found that the rna-seq data contain significant tree structures.
in earlier work  <cit> , we also calculated a statistical measure to show that the distances we computed are in fact representative of a tree.
thus multiple studies on different kinds of datasets—chip-seq in our case, rna-seq in the other two papers—support the tree-like relationship of cell types and underscore the usefulness of the cell-type tree .
prior to these genome-wide computational approaches, hierarchical developmental relationships among cell types were elucidated through a series of laborious experiments involving in vitro differentiation of cell types from various stem cells .
in cell differentiation, both ancestral and derived cell types can coexist within the body.
therefore, it becomes important to be able to infer which cell types should be treated as the ancestor, or parent, of another.
our earlier work  <cit>  focused on the use of distance-based and parsimony-based phylogenetic methods to infer the tree, not the ancestors.
here we propose an ml approach to the inference of cell-type trees on histone modification data and proceed to derive a new algorithm to infer the internal nodes by a process known as lifting.
.
to our knowledge, this is the first lifting approach used in the study of cell differentiation.
we also provide simulations and tests on real data, indicating that our ml approach to the inference of cell-type trees outperforms distance-based and parsimony-based building approaches and that our lifting algorithm not only works well on simulations, but also gives biologically meaningful results.
methods
a histone-modification chip-seq library contains chip-seq data for one chip-seq experiment.
in our case, each library typically contains data for one histone modification for one replicate of a cell type.
our approach to build cell-type trees using a ml framework is illustrated in fig.
<dig>  we explain the various steps below.
fig.
<dig> flowchart for building cell-type trees using a maximum-likelihood framework.
data preprocessing: the mapped reads in the chip-seq data are used to find peaks in the data.
data representation: peak data is converted to a binary matrix using windowing/overlap representation.
phylogenetic analysis: using distance-based, parsimony-based or maximum-likelihood-based phylogenetic approach.
inferring ancestral or internal nodes: we establish a parent-child relationship between the cell types  using a process called lifting
model of differentiation for histone marks
we use the model of  <cit> , in which histone marks can be independently gained or lost in regions of the genome as cells differentiate from a less specialized type to a more specialized one.
this independence assumption is consistent with practice in phylogenetic inference and enormously simplifies computations.
data preprocessing and data representation
chip-seq data are converted into peak data using a peak-finder.
the presence of a peak signifies the presence of a histone mark in that genomic region.
we have used publicly available peak lists  for our study.
to represent the peak data of each cell type, we use two different data representations.
windowing representation: the genome is divided into bins of fixed size; if the bin contains at least one peak, we code it  <dig>  otherwise we code it  <dig>  the coding of each library is thus independent of that of any other library .
we used bins of  <dig> bp because  <dig> bp of dna wrap around the histone and two histones are connected by linker dna of about  <dig> bp; thus each bin approximates the presence or absence of just one histone modification.
overlap representation: this representation takes into account all libraries at once.
the aim is to find interesting regions in the genome based on peaks.
denote the ith peak in library n as pin=piln,pirn, where piln and pirn are the left and right endpoints .
consider each peak as an interval on the genome  and build the interval graph defined by all peaks in all libraries.
an interval graph has one vertex for each interval and an edge between two vertices whenever the two corresponding intervals overlap  <cit> .
we simply want the connected components of the interval graph.
we define an interval in the genome is an interesting region if and only if it corresponds to a connected component of the interval graph.
more details on the overlap representation and an algorithm to identify interesting regions in linear time appear in  <cit> .
the output of either the windowing representation or overlap representation is a string of ones and zeros to represent each data library.
both representations gave fairly similar results in earlier work  <cit> , so in this study we chose the overlap representation, for its compactness.
ml-based phylogenetic analysis
we use an ml-based approach to build cell-type trees on the overlap data representation, carrying out the inference with the raxml tool  <cit> .
we run raxml on the binary data obtained using the overlap representation and obtain a cell-type tree.
for our experiments, we used the gamma model of rate heterogeneity  and turned on the rapid bootstrapping option .
inferring ancestral/internal nodes through lifting
we now describe an algorithm for inferring ancestral/internal nodes using a process called lifting, to establish a parent-child relationship between the various cell types .
lifting techniques have been used in the context of tree alignment problems  <cit> .
we first infer a tree using raxml; we then root the tree using prior biological knowledge.
.
denote by t the resulting rooted binary tree.
we now run the lifting procedure on this tree t, so that they obey path constraints.
the basic idea of the lifting procedure is to compute the likelihood of the tree after the lifting each possible leaf node  and subtract it from the likelihood of the unlifted tree, and then to actually lift the leaf with the highest probability if this difference is greater than some threshold.
the old tree is now updated with the lifted tree and this procedure is continued till the lifting stops.
the pseudocode for the lifting algorithm is given below.
algorithm for lifting
set r=t.
if number of leaves in r is less than or equal to  <dig>  go to step  <dig>
let 𝕃 be the set of leaves whose sibling is also a leaf.
for each leaf node l∈𝕃 we compute the likelihood/probability p of lifting l using the following procedure.
divide the tree r into two smaller trees according to l, rl <dig> and rl <dig> .
rl <dig> is built by first lifting l to its parent and then removing l and its sibling .
rl <dig> is a small tree of  <dig> nodes, the earlier leaf node l which is connected to its sibling node .
fig.
<dig> example of lifting leaf node a  in tree r. tree r is divided into two smaller trees rl <dig> and rl <dig> as described in the algorithm
estimate the probabilities of rl <dig> and rl <dig> .
the total probability is the product of these two probabilities.
compute the best lift l∗=argmaxl∈𝕃p.
let w=log)+αlog−log), where k is the length of the data representation sequence, α a user-defined, real-valued constant, p is the likelihood of tree r. w plays a role similar to a bic criterion  <cit> .
if w> <dig>  we lift, update the tree r=rl∗ <dig>  and mark the corresponding edge  in t as lifted; we then return to step  <dig>
output t and stop.
the output tree t is the desired cell-type tree with labelled ancestral nodes.
we terminate the algorithm when the number of leaves is four or less since we use raxml.
RESULTS
we show the results on both real and simulated data.
using real data
in an earlier work  <cit> , we had shown the usefulness of using cell-type trees on different histone marks from the encode project database: h3k4me <dig>  h3k27me <dig>  h3k4me <dig>  h3k9me <dig>  and h3k27ac.
for testing the lifting algorithm, it is desirable to have as many samples as possible.
we thus focus in this study on histone modification h3k4me <dig>  using chip-seq data for human  from the university of washington encode group  <cit> .
h3k4me <dig> has been assayed in the largest number of cell types and is usually associated with gene activation  <cit> .
table  <dig> gives the list of the  <dig> cell types for which we gathered h3k4me <dig> data.
the cells are classified into groups based on cell type or tissue origin.
is included in the epithelial group).
for human embryonic stem cells  we have data for a differentiation time course in cell culture , so we shall use hesc t <dig> to mean data for hesc cells on day  <dig>  we use only one replicate per cell type for this work.
we use the encode peaks as input to our program.
we convert the input data into 1s and 0s using the overlap representation.
we then use raxml for getting a maximum likelihood based tree.
in this first step, we then compare our results with those obtained with a distance-based approach  and a parsimony-based approach , as explained in  <cit> .
figure  <dig> summarizes the results, using color codes for the major groupings of table  <dig>  in order to quantify the quality of the groupings, we compute the total number of cell types in a subtree that belong to one group.
since our groups are based on cell type only, there could be many subdivisions possible within each group, therefore we choose the two largest such subtrees available for each group such that each subtree contains only the leaf nodes of that group.
fig.
<dig> compares cell-type trees obtained on h3k4me <dig> data  using two different methods on the overlap representation:  using a maximum-likelihood based approach,  using a parsimony-based approach,  using a distance-based approach
table  <dig> groupings for cell-type trees on h3k4me <dig> data
second to ninth columns show the number of cell types  belonging to the largest and second-largest clades; the total number of cell types of that group is in the top row.
rows correspond to various methods.
overlap representation is used.
ml — maximum-likelihood-based approach, p — parsimony-based approach, d — distance-based approach
we now consider a set of  <dig> cell types to evaluate the lifting algorithm  to infer ancestral nodes.
the cell types include the hesc time course of  <dig> days , huvec , hbmec , wi  <dig> , ag <dig> , hpf .
as explained in  <cit> , we expect the following developmental pathways to occur one after the other in time during development:  hesc from days  <dig> to 14;  hesc to huvec to hbmec;  hesc to wi <dig> to ag <dig> to hpf.
we now use the overlap representation and raxml to get the cell-type tree.
the tree was now rooted at the common ancestor of all the embryonic stem cells at different days .
the lifting algorithm is then used.
the α parameter is set high enough such that lifting takes place as much as possible, the larger the value of α the more the number of lifts.
the results are shown in fig.
4b.
we find that there is a path from hesc to huvec to hbmec as expected.
we also find a path from hesc to ag <dig> to hpf.
however we see that wi <dig> could not be lifted before ag <dig>  when we look at the data for hesc data, we see that embryonic stem cells on day  <dig> is an ancestor  to day  <dig>  and day  <dig> is an ancestor to day 14; and we also see day  <dig> is an ancestor to day  <dig>  however day  <dig> is incorrectly lifted above day  <dig>  on the other hand, the fact that day  <dig> ends up on a side branch of the tree is not surprising in view of our previous observation  <cit>  that day  <dig> shows overall increased divergence in histone modification.
this most likely reflects a temporary non-specific response to the growth factor cocktail that was applied on day  <dig> to activate a mesoderm developmental pathway.
fig.
<dig> cell-type trees obtained on h3k4me <dig> data on a set of  <dig> cell types:  before lifting,  after lifting
we repeated these experiments by picking a random number of columns from the overlap representation  and we found that our results are quite consistent, if we choose  <dig>  or even only  <dig>  columns .
using simulated data
in this paper, we use simulated studies to compare the quality of our maximum-likelihood approach and lifting algorithm.
we randomly generate a set of rooted binary trees with a fixed number of leaves — containing either  <dig>   <dig>  and  <dig> leaf nodes .
ten trees for each kind of tree  are generated.
each of these trees then had their edges marked  as lifted  with some probability.
this is the true tree.
data representation length  of  <dig> bits  for each leaf node was then simulated using each tree .
a raxml tree is generated on this leaf data and then this tree is given as input to the lifting program .
for the output tree, each edge which contains a lift from child to parent, is marked as lifted.
this way we can compare the edges in the output tree with the true tree.
edges marked as lifted in the true tree should be shown as lifted in the output tree.
based on this, for each kind of trees , we find the total number of true positives , false positives , true negatives , false negatives .
we measure the following statistics  <cit>  from this information:
true positive rate tpr=tptp+fn.
false positive rate fpr=fpfp+tn.
f-score or f1-score f=2tp2tp+fp+fn
accuracy acc=tp+tntp+tn+fp+fn
we also compute the robinson-foulds metric or rf distance  <cit>  which computes the distance between the true tree and the unlifted tree we get after applying raxml.
the results are shown in table  <dig>  we see that we get high true positive rate, low false positive rate, a reasonably high f-score, and an accuracy of above  <dig> %.
these results thus show that our lifting approach produces good quality results for trees which are both small and large.
since we expect cell-type trees to be build on only a few dozen cell types , we feel the range of tree sizes that we have considered in the simulation study is sufficient.
we also get low rf distances for both 12-leaf and 50-leaf trees.
the slightly higher rf distances we get for 100-leaf tree is because the data representation of  <dig> is not large enough for bigger trees.
tpr
fpr
f
acc
rf
we simulate  <dig> random trees  for each of kind of tree  and ran the lifting algorithm .
we then calculated the following statistics shown in the table: true positive rate , false positive rate , f-score or f
1-score , accuracy , rf distance
to show the robustness of our approach, we repeat the above experiments  by varying the length of data representation  per cell type.
we use the following values —  <dig>   <dig>  and  <dig> bits for each node.
various statistics are calculated by fixing the α threshold to  <dig> .
the results are shown in table  <dig>  we find that the different statistics are stable across different data representation lengths and the accuracy is around  <dig> %, and the statistics  improve with larger k which is expected.
the rf distance is around  <dig> for different values of k. this shows that the threshold α is stable for a large variation of data representation lengths.
we note that the choice of threshold α is dependent on the dataset used.
the larger the value of α the greater the chances of lifting.
for example if all the datasets for whose cell-type tree we are building are cell types which share a lineage in development, then we would like to lift as many cell types as possible; however if the dataset considered has only one or two cell types which have a lineage in cell-development then we would expect less lifting.
so the value of α can be set by the biologist based on biological knowledge, since our method can be used as an exploratory tool.
the value of α also depends on the length of the data representation, though it is robust over a reasonably wide range of data-representation as shown in table  <dig>  now we show that for a fixed length of data representation, we can vary α parameters over a reasonably wide range.
the results are shown in table  <dig>  in this experiment we fixed k= <dig>  and simulated these data values for each of the 12-leaf trees and randomly chose lifting paths.
we see from the table that even when α values vary from  <dig>  to  <dig>  the various statistics calculated have stable values.
this shows the robustness of the parameters in our method.
tpr
fpr
f
acc
rf
we simulate  <dig> random 12-leaf trees for varying number of data representation lengths  and ran the lifting algorithm .
we then calculated the following statistics shown in the table: true positive rate , false positive rate , f-score or f
1-score , accuracy , rf distance
tpr
fpr
f
acc
we simulate  <dig> random 12-leaf trees for data representation length of size  <dig> and ran the lifting algorithm for varying values of α. we then calculated the following statistics shown in the table: true positive rate , false positive rate , f-score or f
1-score , accuracy
CONCLUSIONS
we proposed a maximum-likelihood based approach to estimate cell-type trees from histone modification data.
we showed that our maximum-likelihood based approach outperforms previous approaches such as distance-based or parsimony-based methods, on h3k4me <dig> histone modification data.
we also proposed the first lifting-based approach to infer internal nodes in cell-type trees and showed the usefulness of this technique in both real and simulated data.
the lifting approach is important since in cell differentiation, ancestral cell types can coexist with derived cell types in adult organisms.
our approach is easy to use and is probably the only current approach to build cell-type trees with ancestral inference.
hence we feel that our approach will be an effective way to help biologists and bioinformaticians to study the cell differentiation process.
the lifting process we developed may also have many other applications, be in the study of cancer genetic data where normal cells differentiate into cancerous cells, and in other diverse fields like the evolution of languages.
availability of supporting data
the code for this work can be downloaded from http://lcbb.epfl.ch/software.html.
from the fourteenth asia pacific bioinformatics conference san francisco, ca, usa.
11– <dig> january 2016
competing interests
the authors declare that they have no competing interests.
authors’ contributions
the research problem was defined by: nun, pb, bmem.
designed the methods and algorithms: nun, ms, lh, pg, yl, bmem.
the experimental design was done by: nun, lh, ms, pb, bmem.
methods implemented by nun, lh, pg.
carried out the experiments: nun, lh.
analyzed the data: nun, lh, ms, yl, pb, bmem.
nun, bmem wrote the paper with help from all the other authors.
all authors read and approved the final manuscript.

 cell differentiation is the process by which a less specialized cell becomes a more specialized one; it often proceeds in a hierarchical manner, with totipotent cells sequentially committing to fates of more restricted developmental potential. epigenetic and transcription factors play a significant role in cell differentiation, therefore motivating a study of epigenetic changes across different cell types. arendt proposed a sister-cell-type model for the hierarchical relationship between cell types. in this model, “novel cell types arise in pairs from an ancestral cell type through sub-specialization”. under this model, the evolutionary relatedness of cell types is expected to be congruent with the ontogenetic hierarchy of cellular differentiation, because the “development of the sister cell types is the same up to the last stages of differentiation”. the authors claim that multifunctionality has been a general feature of ancient cell types and that, with “increasing specialization during evolution, these multiple functions were then distributed in a complementary manner to sister cell types”. evolution and cell differentiation share a number of attributes. first, as mentioned before, we know that cell differentiation transforms less specialized cell types into more specialized ones. since this transformation is unidirectional, the paths of differentiation can be represented as a tree structure, much as is done with the phylogenetic trees used to represent evolutionary histories. the similarity between the two extends further: cell types themselves have evolved into larger collections from more restricted collections in early ancestors: there are phylogenetic relationships among the various types of cells. second, observed changes in the epigenetic state are inheritable, again much as mutations in the genome are; and finally, epigenetic traits are subject to stochastic changes. one major difference between evolution and cell differentiation is that functional changes in cell differentiation are primarily driven by programmed mutational events rather than by selection. however, the program of mutational events is itself the result of evolution, so that, as observed by, the cell differentiation tree often recapitulates the phylogeny of cell types. we focus here on one important epigenetic mark—histone modification. histones are proteins that package the dna into nucleosomes. these proteins are subjected to various types of chemical modifications, called histone modifications, such as methylation, acetylation, phosphorylation, ubiquitination, etc. these modifications alter their interactions with the dna and thereby influence transcription and genomic function. histone modifications have been found to vary across cell types and to play an important role in gene regulation. since histones are present in every bp length of dna, we need genome-wide high-throughput technologies to study the modifications of these proteins. chip-seq is such a technology. the study of chip-seq histone modification data can help us understand the role of histone modifications in developmental biology and cell differentiation. the term “cell-type tree” was defined by our group to refer to a tree relationship between various cell types. the nodes of this tree represent cell types while the edges represent directed differentiation/evolution events from one cell type to another. we know that the genome is consistent across cell types of the same individual and that it is also highly similar between individuals of the same species, but that epigenomic states of various regions of the genome differ across various cell types. these epigenomic states are believed to affect cell differentiation process through a complex interplay between histone modifications, dna methylation, transcription factors, etc. kin et al. recently constructed a cell-type tree using rna-seq data and a parsimony-based approach under assumptions very similar to ours, using the same term of “cell-type tree” to denote the “hypothetical tree-like relationship of cell types in ontogeny and phylogeny”. liang et al. recently developed a statistical model for cell differentiation and applied it to encode and fantom rna-seq data. as in kin et al. work, they found that the rna-seq data contain significant tree structures. in earlier work, we also calculated a statistical measure to show that the distances we computed are in fact representative of a tree. thus multiple studies on different kinds of datasets—chip-seq in our case, rna-seq in the other two papers—support the tree-like relationship of cell types and underscore the usefulness of the cell-type tree. prior to these genome-wide computational approaches, hierarchical developmental relationships among cell types were elucidated through a series of laborious experiments involving in vitro differentiation of cell types from various stem cells. in cell differentiation, both ancestral and derived cell types can coexist within the body. therefore, it becomes important to be able to infer which cell types should be treated as the ancestor, or parent, of another. our earlier work focused on the use of distance-based and parsimony-based phylogenetic methods to infer the tree, not the ancestors. here we propose an ml approach to the inference of cell-type trees on histone modification data and proceed to derive a new algorithm to infer the internal nodes by a process known as lifting.. to our knowledge, this is the first lifting approach used in the study of cell differentiation. we also provide simulations and tests on real data, indicating that our ml approach to the inference of cell-type trees outperforms distance-based and parsimony-based building approaches and that our lifting algorithm not only works well on simulations, but also gives biologically meaningful results. methods a histone-modification chip-seq library contains chip-seq data for one chip-seq experiment. in our case, each library typically contains data for one histone modification for one replicate of a cell type. our approach to build cell-type trees using a ml framework is illustrated in fig. we explain the various steps below. fig. flowchart for building cell-type trees using a maximum-likelihood framework. data preprocessing: the mapped reads in the chip-seq data are used to find peaks in the data. data representation: peak data is converted to a binary matrix using windowing/overlap representation. phylogenetic analysis: using distance-based, parsimony-based or maximum-likelihood-based phylogenetic approach. inferring ancestral or internal nodes: we establish a parent-child relationship between the cell types using a process called lifting model of differentiation for histone marks we use the model of, in which histone marks can be independently gained or lost in regions of the genome as cells differentiate from a less specialized type to a more specialized one. this independence assumption is consistent with practice in phylogenetic inference and enormously simplifies computations. data preprocessing and data representation chip-seq data are converted into peak data using a peak-finder. the presence of a peak signifies the presence of a histone mark in that genomic region. we have used publicly available peak lists for our study. to represent the peak data of each cell type, we use two different data representations. windowing representation: the genome is divided into bins of fixed size; if the bin contains at least one peak, we code it otherwise we code it the coding of each library is thus independent of that of any other library. we used bins of bp because bp of dna wrap around the histone and two histones are connected by linker dna of about bp; thus each bin approximates the presence or absence of just one histone modification. overlap representation: this representation takes into account all libraries at once. the aim is to find interesting regions in the genome based on peaks. denote the ith peak in library n as pin=piln,pirn, where piln and pirn are the left and right endpoints. consider each peak as an interval on the genome and build the interval graph defined by all peaks in all libraries. an interval graph has one vertex for each interval and an edge between two vertices whenever the two corresponding intervals overlap. we simply want the connected components of the interval graph. we define an interval in the genome is an interesting region if and only if it corresponds to a connected component of the interval graph. more details on the overlap representation and an algorithm to identify interesting regions in linear time appear in. the output of either the windowing representation or overlap representation is a string of ones and zeros to represent each data library. both representations gave fairly similar results in earlier work, so in this study we chose the overlap representation, for its compactness. ml-based phylogenetic analysis we use an ml-based approach to build cell-type trees on the overlap data representation, carrying out the inference with the raxml tool. we run raxml on the binary data obtained using the overlap representation and obtain a cell-type tree. for our experiments, we used the gamma model of rate heterogeneity and turned on the rapid bootstrapping option. inferring ancestral/internal nodes through lifting we now describe an algorithm for inferring ancestral/internal nodes using a process called lifting, to establish a parent-child relationship between the various cell types. lifting techniques have been used in the context of tree alignment problems. we first infer a tree using raxml; we then root the tree using prior biological knowledge.. denote by t the resulting rooted binary tree. we now run the lifting procedure on this tree t, so that they obey path constraints. the basic idea of the lifting procedure is to compute the likelihood of the tree after the lifting each possible leaf node and subtract it from the likelihood of the unlifted tree, and then to actually lift the leaf with the highest probability if this difference is greater than some threshold. the old tree is now updated with the lifted tree and this procedure is continued till the lifting stops. the pseudocode for the lifting algorithm is given below. algorithm for lifting set r=t. if number of leaves in r is less than or equal to go to step let 𝕃 be the set of leaves whose sibling is also a leaf. for each leaf node l∈𝕃 we compute the likelihood/probability p of lifting l using the following procedure. divide the tree r into two smaller trees according to l, rl and rl. rl is built by first lifting l to its parent and then removing l and its sibling. rl is a small tree of nodes, the earlier leaf node l which is connected to its sibling node. fig. example of lifting leaf node a in tree r. tree r is divided into two smaller trees rl and rl as described in the algorithm estimate the probabilities of rl and rl. the total probability is the product of these two probabilities. compute the best lift l∗=argmaxl∈𝕃p. let w=log)+αlog−log), where k is the length of the data representation sequence, α a user-defined, real-valued constant, p is the likelihood of tree r. w plays a role similar to a bic criterion. if w> we lift, update the tree r=rl∗ and mark the corresponding edge in t as lifted; we then return to step output t and stop. the output tree t is the desired cell-type tree with labelled ancestral nodes. we terminate the algorithm when the number of leaves is four or less since we use raxml.  we show the results on both real and simulated data. using real data in an earlier work, we had shown the usefulness of using cell-type trees on different histone marks from the encode project database: h3k4me h3k27me h3k4me h3k9me and h3k27ac. for testing the lifting algorithm, it is desirable to have as many samples as possible. we thus focus in this study on histone modification h3k4me using chip-seq data for human from the university of washington encode group. h3k4me has been assayed in the largest number of cell types and is usually associated with gene activation. table gives the list of the cell types for which we gathered h3k4me data. the cells are classified into groups based on cell type or tissue origin. is included in the epithelial group). for human embryonic stem cells we have data for a differentiation time course in cell culture, so we shall use hesc t to mean data for hesc cells on day we use only one replicate per cell type for this work. we use the encode peaks as input to our program. we convert the input data into 1s and 0s using the overlap representation. we then use raxml for getting a maximum likelihood based tree. in this first step, we then compare our results with those obtained with a distance-based approach and a parsimony-based approach, as explained in. figure summarizes the results, using color codes for the major groupings of table in order to quantify the quality of the groupings, we compute the total number of cell types in a subtree that belong to one group. since our groups are based on cell type only, there could be many subdivisions possible within each group, therefore we choose the two largest such subtrees available for each group such that each subtree contains only the leaf nodes of that group. fig. compares cell-type trees obtained on h3k4me data using two different methods on the overlap representation: using a maximum-likelihood based approach, using a parsimony-based approach, using a distance-based approach table groupings for cell-type trees on h3k4me data second to ninth columns show the number of cell types belonging to the largest and second-largest clades; the total number of cell types of that group is in the top row. rows correspond to various methods. overlap representation is used. ml — maximum-likelihood-based approach, p — parsimony-based approach, d — distance-based approach we now consider a set of cell types to evaluate the lifting algorithm to infer ancestral nodes. the cell types include the hesc time course of days, huvec, hbmec, wi, ag, hpf. as explained in, we expect the following developmental pathways to occur one after the other in time during development: hesc from days to 14; hesc to huvec to hbmec; hesc to wi to ag to hpf. we now use the overlap representation and raxml to get the cell-type tree. the tree was now rooted at the common ancestor of all the embryonic stem cells at different days. the lifting algorithm is then used. the α parameter is set high enough such that lifting takes place as much as possible, the larger the value of α the more the number of lifts. the results are shown in fig. 4b. we find that there is a path from hesc to huvec to hbmec as expected. we also find a path from hesc to ag to hpf. however we see that wi could not be lifted before ag when we look at the data for hesc data, we see that embryonic stem cells on day is an ancestor to day and day is an ancestor to day 14; and we also see day is an ancestor to day however day is incorrectly lifted above day on the other hand, the fact that day ends up on a side branch of the tree is not surprising in view of our previous observation that day shows overall increased divergence in histone modification. this most likely reflects a temporary non-specific response to the growth factor cocktail that was applied on day to activate a mesoderm developmental pathway. fig. cell-type trees obtained on h3k4me data on a set of cell types: before lifting, after lifting we repeated these experiments by picking a random number of columns from the overlap representation and we found that our results are quite consistent, if we choose or even only columns. using simulated data in this paper, we use simulated studies to compare the quality of our maximum-likelihood approach and lifting algorithm. we randomly generate a set of rooted binary trees with a fixed number of leaves — containing either and leaf nodes. ten trees for each kind of tree are generated. each of these trees then had their edges marked as lifted with some probability. this is the true tree. data representation length of bits for each leaf node was then simulated using each tree. a raxml tree is generated on this leaf data and then this tree is given as input to the lifting program. for the output tree, each edge which contains a lift from child to parent, is marked as lifted. this way we can compare the edges in the output tree with the true tree. edges marked as lifted in the true tree should be shown as lifted in the output tree. based on this, for each kind of trees, we find the total number of true positives, false positives, true negatives, false negatives. we measure the following statistics from this information: true positive rate tpr=tptp+fn. false positive rate fpr=fpfp+tn. f-score or f1-score f=2tp2tp+fp+fn accuracy acc=tp+tntp+tn+fp+fn we also compute the robinson-foulds metric or rf distance which computes the distance between the true tree and the unlifted tree we get after applying raxml. the results are shown in table we see that we get high true positive rate, low false positive rate, a reasonably high f-score, and an accuracy of above %. these results thus show that our lifting approach produces good quality results for trees which are both small and large. since we expect cell-type trees to be build on only a few dozen cell types, we feel the range of tree sizes that we have considered in the simulation study is sufficient. we also get low rf distances for both 12-leaf and 50-leaf trees. the slightly higher rf distances we get for 100-leaf tree is because the data representation of is not large enough for bigger trees. tpr fpr f acc rf we simulate random trees for each of kind of tree and ran the lifting algorithm. we then calculated the following statistics shown in the table: true positive rate, false positive rate, f-score or f 1-score, accuracy, rf distance to show the robustness of our approach, we repeat the above experiments by varying the length of data representation per cell type. we use the following values — and bits for each node. various statistics are calculated by fixing the α threshold to. the results are shown in table we find that the different statistics are stable across different data representation lengths and the accuracy is around %, and the statistics improve with larger k which is expected. the rf distance is around for different values of k. this shows that the threshold α is stable for a large variation of data representation lengths. we note that the choice of threshold α is dependent on the dataset used. the larger the value of α the greater the chances of lifting. for example if all the datasets for whose cell-type tree we are building are cell types which share a lineage in development, then we would like to lift as many cell types as possible; however if the dataset considered has only one or two cell types which have a lineage in cell-development then we would expect less lifting. so the value of α can be set by the biologist based on biological knowledge, since our method can be used as an exploratory tool. the value of α also depends on the length of the data representation, though it is robust over a reasonably wide range of data-representation as shown in table now we show that for a fixed length of data representation, we can vary α parameters over a reasonably wide range. the results are shown in table in this experiment we fixed k= and simulated these data values for each of the 12-leaf trees and randomly chose lifting paths. we see from the table that even when α values vary from to the various statistics calculated have stable values. this shows the robustness of the parameters in our method. tpr fpr f acc rf we simulate random 12-leaf trees for varying number of data representation lengths and ran the lifting algorithm. we then calculated the following statistics shown in the table: true positive rate, false positive rate, f-score or f 1-score, accuracy, rf distance tpr fpr f acc we simulate random 12-leaf trees for data representation length of size and ran the lifting algorithm for varying values of α. we then calculated the following statistics shown in the table: true positive rate, false positive rate, f-score or f 1-score, accuracy  we proposed a maximum-likelihood based approach to estimate cell-type trees from histone modification data. we showed that our maximum-likelihood based approach outperforms previous approaches such as distance-based or parsimony-based methods, on h3k4me histone modification data. we also proposed the first lifting-based approach to infer internal nodes in cell-type trees and showed the usefulness of this technique in both real and simulated data. the lifting approach is important since in cell differentiation, ancestral cell types can coexist with derived cell types in adult organisms. our approach is easy to use and is probably the only current approach to build cell-type trees with ancestral inference. hence we feel that our approach will be an effective way to help biologists and bioinformaticians to study the cell differentiation process. the lifting process we developed may also have many other applications, be in the study of cancer genetic data where normal cells differentiate into cancerous cells, and in other diverse fields like the evolution of languages. availability of supporting data the code for this work can be downloaded from http://lcbb.epfl.ch/software.html. from the fourteenth asia pacific bioinformatics conference san francisco, ca, usa. 11– january 2016 competing interests the authors declare that they have no competing interests. authors’ contributions the research problem was defined by: nun, pb, bmem. designed the methods and algorithms: nun, ms, lh, pg, yl, bmem. the experimental design was done by: nun, lh, ms, pb, bmem. methods implemented by nun, lh, pg. carried out the experiments: nun, lh. analyzed the data: nun, lh, ms, yl, pb, bmem. nun, bmem wrote the paper with help from all the other authors. all authors read and approved the final manuscript. 
we propose a maximum-likelihood approach to build cell-type trees and show that this ml approach outperforms our earlier distance-based and parsimony-based approaches. we show that our ml-based approach outperforms previously proposed techniques such as distance-based and parsimony-based methods. epigenetic factors such as histone modifications are known to play a significant role in cell differentiation. we then study the reconstruction of ancestral cell types; since both ancestral and derived cell types can coexist in adult organisms, we propose a lifting algorithm to infer internal nodes. we present results on our lifting algorithm obtained both through simulations and on real datasets. we show our lifting-based approach works well on both simulated and real data. we previously introduce cell-type trees to represent the differentiation of cells into more specialized types, a representation that partakes of both ontogeny and phylogeny. cell-type treeshistone modificationsepigenomicsphylogenyevolutioncell-differentiationthe fourteenth asia pacific bioinformatics conference apbc 2016san francisco, ca, usa - january http://www.sfasa.org/apbc2016/apbc htmlissue-copyright-statement© the author 2016 in cell differentiation, a less specialized cell differentiates into a more specialized one, even though all cells in one organism have the same genome.
 in cell differentiation, a less specialized cell differentiates into a more specialized one, even though all cells in one organism have the same genome. epigenetic factors such as histone modifications are known to play a significant role in cell differentiation. we previously introduce cell-type trees to represent the differentiation of cells into more specialized types, a representation that partakes of both ontogeny and phylogeny.  we propose a maximum-likelihood approach to build cell-type trees and show that this ml approach outperforms our earlier distance-based and parsimony-based approaches. we then study the reconstruction of ancestral cell types; since both ancestral and derived cell types can coexist in adult organisms, we propose a lifting algorithm to infer internal nodes. we present results on our lifting algorithm obtained both through simulations and on real datasets.  we show that our ml-based approach outperforms previously proposed techniques such as distance-based and parsimony-based methods. we show our lifting-based approach works well on both simulated and real data. keywords cell-type treeshistone modificationsepigenomicsphylogenyevolutioncell-differentiationthe fourteenth asia pacific bioinformatics conference apbc 2016san francisco, ca, usa - january http://www.sfasa.org/apbc2016/apbc htmlissue-copyright-statement© the author 2016 