{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,12]],"date-time":"2026-04-12T06:41:24Z","timestamp":1775976084396,"version":"3.50.1"},"reference-count":26,"publisher":"Oxford University Press (OUP)","issue":"20","license":[{"start":{"date-parts":[[2017,6,5]],"date-time":"2017-06-05T00:00:00Z","timestamp":1496620800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017,10,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:sec>\n                    <jats:title>Motivation<\/jats:title>\n                    <jats:p>The identification of heterogeneities in cell populations by utilizing single-cell technologies such as single-cell RNA-Seq, enables inference of cellular development and lineage trees. Several methods have been proposed for such inference from high-dimensional single-cell data. They typically assign each cell to a branch in a differentiation trajectory. However, they commonly assume specific geometries such as tree-like developmental hierarchies and lack statistically sound methods to decide on the number of branching events.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Results<\/jats:title>\n                    <jats:p>We present K-Branches, a solution to the above problem by locally fitting half-lines to single-cell data, introducing a clustering algorithm similar to K-Means. These halflines are proxies for branches in the differentiation trajectory of cells. We propose a modified version of the GAP statistic for model selection, in order to decide on the number of lines that best describe the data locally. In this manner, we identify the location and number of subgroups of cells that are associated with branching events and full differentiation, respectively. We evaluate the performance of our method on single-cell RNA-Seq data describing the differentiation of myeloid progenitors during hematopoiesis, single-cell qPCR data of mouse blastocyst development, single-cell qPCR data of human myeloid monocytic leukemia and artificial data.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Availability and implementation<\/jats:title>\n                    <jats:p>An R implementation of K-Branches is freely available at https:\/\/github.com\/theislab\/kbranches.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Supplementary information<\/jats:title>\n                    <jats:p>Supplementary data are available at Bioinformatics online.<\/jats:p>\n                  <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btx325","type":"journal-article","created":{"date-parts":[[2017,5,31]],"date-time":"2017-05-31T07:08:53Z","timestamp":1496214533000},"page":"3211-3219","source":"Crossref","is-referenced-by-count":14,"title":["Model-based branching point detection in single-cell data by K-branches clustering"],"prefix":"10.1093","volume":"33","author":[{"given":"Nikolaos K","family":"Chlis","sequence":"first","affiliation":[{"name":"Institute of Computational Biology, Helmholtz Zentrum M\u00fcnchen, Neuherberg, Germany"},{"name":"School of Life Sciences Weihenstephan, Technical University of Munich, Freising, Germany"}]},{"given":"F Alexander","family":"Wolf","sequence":"additional","affiliation":[{"name":"Institute of Computational Biology, Helmholtz Zentrum M\u00fcnchen, Neuherberg, Germany"}]},{"given":"Fabian J","family":"Theis","sequence":"additional","affiliation":[{"name":"Institute of Computational Biology, Helmholtz Zentrum M\u00fcnchen, Neuherberg, Germany"},{"name":"School of Life Sciences Weihenstephan, Technical University of Munich, Freising, Germany"},{"name":"Department of Mathematics, Technical University of Munich, Garching, Germany"}]}],"member":"286","published-online":{"date-parts":[[2017,6,5]]},"reference":[{"key":"2023020207521319600_btx325-B1","doi-asserted-by":"crossref","first-page":"714","DOI":"10.1016\/j.cell.2014.04.005","article-title":"Single-cell trajectory detection uncovers progression and regulatory coordination in human b cell development","volume":"157","author":"Bendall","year":"2014","journal-title":"Cell"},{"key":"2023020207521319600_btx325-B2","doi-asserted-by":"crossref","first-page":"7426","DOI":"10.1073\/pnas.0500334102","article-title":"Geometric diffusions as a tool for harmonic analysis and structure definition of data: diffusion maps","volume":"102","author":"Coifman","year":"2005","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2023020207521319600_btx325-B3","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1016\/j.copbio.2014.10.010","article-title":"Computational and experimental single cell biology techniques for the definition of cell type heterogeneity, interplay and intracellular dynamics","volume":"34","author":"de Vargas Roditi","year":"2015","journal-title":"Curr. Opin. Biotechnol"},{"key":"2023020207521319600_btx325-B4","doi-asserted-by":"crossref","first-page":"799","DOI":"10.1016\/j.cell.2015.10.039","article-title":"Design and analysis of single-cell sequencing experiments","volume":"163","author":"Gr\u00fcn","year":"2015","journal-title":"Cell"},{"key":"2023020207521319600_btx325-B5","doi-asserted-by":"crossref","first-page":"675","DOI":"10.1016\/j.devcel.2010.02.012","article-title":"Resolution of cell fate decisions revealed by single-cell gene expression analysis from zygote to blastocyst","volume":"18","author":"Guo","year":"2010","journal-title":"Develop. Cell"},{"key":"2023020207521319600_btx325-B6","doi-asserted-by":"crossref","first-page":"2989","DOI":"10.1093\/bioinformatics\/btv325","article-title":"Diffusion maps for high-dimensional single-cell analysis of differentiation data","volume":"31","author":"Haghverdi","year":"2015","journal-title":"Bioinformatics"},{"key":"2023020207521319600_btx325-B7","doi-asserted-by":"crossref","first-page":"845","DOI":"10.1038\/nmeth.3971","article-title":"Diffusion pseudotime robustly reconstructs lineage branching","volume":"13","author":"Haghverdi","year":"2016","journal-title":"Nat. Methods"},{"key":"2023020207521319600_btx325-B8","doi-asserted-by":"crossref","DOI":"10.1007\/978-0-387-84858-7","volume-title":"The Elements of Statistical Learning: data Mining, Inference, and Prediction","author":"Hastie","year":"2009"},{"key":"2023020207521319600_btx325-B9","doi-asserted-by":"crossref","first-page":"776","DOI":"10.1126\/science.1247651","article-title":"Massively parallel single-cell rna-seq for marker-free decomposition of tissues into cell types","volume":"343","author":"Jaitin","year":"2014","journal-title":"Science"},{"key":"2023020207521319600_btx325-B10","doi-asserted-by":"crossref","first-page":"e117.","DOI":"10.1093\/nar\/gkw430","article-title":"Tscan: pseudo-time reconstruction and evaluation in single-cell rna-seq analysis","volume":"44","author":"Ji","year":"2016","journal-title":"Nucleic Acids Res"},{"key":"2023020207521319600_btx325-B11","doi-asserted-by":"crossref","first-page":"483","DOI":"10.1038\/nmeth.4236","article-title":"Sc3 - consensus clustering of single-cell rna-seq data","volume":"14","author":"Kiselev","year":"2017","journal-title":"Nat. Meth."},{"key":"2023020207521319600_btx325-B12","doi-asserted-by":"crossref","first-page":"R118.","DOI":"10.1186\/gb-2013-14-10-r118","article-title":"Temporal dynamics and transcriptional control using single-cell gene expression analysis","volume":"14","author":"Kouno","year":"2013","journal-title":"Genome Biol"},{"key":"2023020207521319600_btx325-B13","doi-asserted-by":"crossref","first-page":"1130","DOI":"10.1016\/j.celrep.2014.04.011","article-title":"Single-cell rna sequencing reveals t helper cells synthesizing steroids de novo to contribute to immune homeostasis","volume":"7","author":"Mahata","year":"2014","journal-title":"Cell Rep"},{"key":"2023020207521319600_btx325-B14","author":"Mohajer","year":"2010"},{"key":"2023020207521319600_btx325-B15","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1038\/nbt.3154","article-title":"Decoding the regulatory network of early blood development from single-cell gene expression measurements","volume":"33","author":"Moignard","year":"2015","journal-title":"Nat. Biotech"},{"key":"2023020207521319600_btx325-B16","doi-asserted-by":"crossref","first-page":"1663","DOI":"10.1016\/j.cell.2015.11.013","article-title":"Transcriptional heterogeneity and lineage commitment in myeloid progenitors","volume":"163","author":"Paul","year":"2015","journal-title":"Cell"},{"key":"2023020207521319600_btx325-B17","first-page":"1","article-title":"Single-cell analysis of cd4+ t-cell differentiation reveals three major cell states and progressive acceleration of proliferation","volume":"17","author":"Proserpio","year":"2016","journal-title":"Genome Biol"},{"key":"2023020207521319600_btx325-B18","doi-asserted-by":"crossref","first-page":"2323","DOI":"10.1126\/science.290.5500.2323","article-title":"Nonlinear dimensionality reduction by locally linear embedding","volume":"290","author":"Roweis","year":"2000","journal-title":"Science"},{"key":"2023020207521319600_btx325-B19","doi-asserted-by":"crossref","first-page":"637","DOI":"10.1038\/nbt.3569","article-title":"Wishbone identifies bifurcating developmental trajectories from single-cell data","volume":"34","author":"Setty","year":"2016","journal-title":"Nat. Biotech"},{"key":"2023020207521319600_btx325-B20","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1038\/nrg3833","article-title":"Computational and analytical challenges in single-cell transcriptomics","volume":"16","author":"Stegle","year":"2015","journal-title":"Nat. Rev. Genet"},{"key":"2023020207521319600_btx325-B21","volume-title":"Pattern Recognition","author":"Theodoridis","year":"2008","edition":"4th edn."},{"key":"2023020207521319600_btx325-B22","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1111\/1467-9868.00293","article-title":"Estimating the number of clusters in a data set via the gap statistic","volume":"63","author":"Tibshirani","year":"2001","journal-title":"J. R Stat. Soc. Ser. B (Stat. Methodol.)"},{"key":"2023020207521319600_btx325-B23","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1038\/nbt.2859","article-title":"The dynamics and regulators of cell fate decisions are revealed by pseudotemporal ordering of single cells","volume":"32","author":"Trapnell","year":"2014","journal-title":"Nat. Biotech"},{"key":"2023020207521319600_btx325-B24","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1038\/150563a0","article-title":"Canalization of development and the inheritance of acquired characters","volume":"150","author":"Waddington","year":"1942","journal-title":"Nature"},{"key":"2023020207521319600_btx325-B25","volume-title":"The Strategy of the Genes. A Discussion of Some Aspects of Theoretical Biology","author":"Waddington","year":"1957"},{"key":"2023020207521319600_btx325-B26","doi-asserted-by":"crossref","first-page":"106.","DOI":"10.1186\/s13059-016-0975-3","article-title":"Slicer: inferring branched, nonlinear cellular trajectories from single cell rna-seq data","volume":"17","author":"Welch","year":"2016","journal-title":"Genome Biol"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/33\/20\/3211\/49042992\/bioinformatics_33_20_3211.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/33\/20\/3211\/49042992\/bioinformatics_33_20_3211.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,2]],"date-time":"2023-02-02T02:58:36Z","timestamp":1675306716000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/33\/20\/3211\/3861329"}},"subtitle":[],"editor":[{"given":"Ziv","family":"Bar-Joseph","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2017,6,5]]},"references-count":26,"journal-issue":{"issue":"20","published-print":{"date-parts":[[2017,10,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btx325","relation":{"has-preprint":[{"id-type":"doi","id":"10.1101\/094532","asserted-by":"object"}]},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2017,10,15]]},"published":{"date-parts":[[2017,6,5]]}}}