{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T01:47:01Z","timestamp":1760233621588,"version":"build-2065373602"},"reference-count":42,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2021,2,5]],"date-time":"2021-02-05T00:00:00Z","timestamp":1612483200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100002347","name":"Bundesministerium f\u00fcr Bildung und Forschung","doi-asserted-by":"publisher","award":["031A538B","031L0164C"],"award-info":[{"award-number":["031A538B","031L0164C"]}],"id":[{"id":"10.13039\/501100002347","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["AX 84\/4-1 & STA 850\/30-1"],"award-info":[{"award-number":["AX 84\/4-1 & STA 850\/30-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Lebanese Association for Scientific Research","award":["(N\/A)"],"award-info":[{"award-number":["(N\/A)"]}]},{"DOI":"10.13039\/501100014913","name":"Freistaat Sachsen","doi-asserted-by":"publisher","award":["Landesgraduiertenstipendium"],"award-info":[{"award-number":["Landesgraduiertenstipendium"]}],"id":[{"id":"10.13039\/501100014913","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computation"],"abstract":"<jats:p>The problem of segmenting linearly ordered data is frequently encountered in time-series analysis, computational biology, and natural language processing. Segmentations obtained independently from replicate data sets or from the same data with different methods or parameter settings pose the problem of computing an aggregate or consensus segmentation. This Segmentation Aggregation problem amounts to finding a segmentation that minimizes the sum of distances to the input segmentations. It is again a segmentation problem and can be solved by dynamic programming. The aim of this contribution is (1) to gain a better mathematical understanding of the Segmentation Aggregation problem and its solutions and (2) to demonstrate that consensus segmentations have useful applications. Extending previously known results we show that for a large class of distance functions only breakpoints present in at least one input segmentation appear in the consensus segmentation. Furthermore, we derive a bound on the size of consensus segments. As show-case applications, we investigate a yeast transcriptome and show that consensus segments provide a robust means of identifying transcriptomic units. This approach is particularly suited for dense transcriptomes with polycistronic transcripts, operons, or a lack of separation between transcripts. As a second application, we demonstrate that consensus segmentations can be used to robustly identify growth regimes from sets of replicate growth curves.<\/jats:p>","DOI":"10.3390\/computation9020017","type":"journal-article","created":{"date-parts":[[2021,2,5]],"date-time":"2021-02-05T03:34:02Z","timestamp":1612496042000},"page":"17","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Weighted Consensus Segmentations"],"prefix":"10.3390","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3013-9340","authenticated-orcid":false,"given":"Halima","family":"Saker","sequence":"first","affiliation":[{"name":"Bioinformatics Group, Department of Computer Science, and Interdisciplinary Center for Bioinformatics, Universit\u00e4t Leipzig, D-04107 Leipzig, Germany"},{"name":"Doctoral School of Science and Technology, Lebanese University, Tripoli, Lebanon"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1274-5099","authenticated-orcid":false,"given":"Rainer","family":"Machn\u00e9","sequence":"additional","affiliation":[{"name":"Institute for Synthetic Microbiology and Institute for Quantitative and Theoretical Biology, Heinrich Heine University, D-40225 D\u00fcsseldorf, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4573-9939","authenticated-orcid":false,"given":"J\u00f6rg","family":"Fallmann","sequence":"additional","affiliation":[{"name":"Bioinformatics Group, Department of Computer Science, and Interdisciplinary Center for Bioinformatics, Universit\u00e4t Leipzig, D-04107 Leipzig, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Douglas B.","family":"Murray","sequence":"additional","affiliation":[{"name":"Lakeland University Japan Shinjuku-ku, Tokyo 160-0022, Japan"},{"name":"University of Maryland Global Campus\u2014Asia, Yokota Air Base, Fussa-shi, Tokyo 197-0001, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4704-3035","authenticated-orcid":false,"given":"Ahmad M.","family":"Shahin","sequence":"additional","affiliation":[{"name":"Doctoral School of Science and Technology, Lebanese University, Tripoli, Lebanon"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5016-5191","authenticated-orcid":false,"given":"Peter F.","family":"Stadler","sequence":"additional","affiliation":[{"name":"Bioinformatics Group, Department of Computer Science, and Interdisciplinary Center for Bioinformatics, Universit\u00e4t Leipzig, D-04107 Leipzig, Germany"},{"name":"German Centre for Integrative Biodiversity Research (iDiv) Halle-Jena-Leipzig, Competence Center for Scalable Data Services and Solutions, Leipzig Research Center for Civilization Diseases, and Leipzig Research Center for Civilization Diseases (LIFE), Leipzig University, D-04103 Leipzig, Germany"},{"name":"Institute for Theoretical Chemistry, University of Vienna, A-1090 Wien, Austria"},{"name":"Facultad de Ciencias, Universidad National de Colombia, Bogot\u00e1 CO-111321, Colombia"},{"name":"Santa Fe Institute, Santa Fe, NM 87501, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2021,2,5]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"138","DOI":"10.3389\/fgene.2015.00138","article-title":"Whole-genome CNV analysis: Advances in computational approaches","volume":"6","author":"Pirooznia","year":"2015","journal-title":"Front. Genet."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"7973","DOI":"10.1038\/ncomms8973","article-title":"Systematic chromatin state comparison of epigenomes associated with diverse properties including sex and tissue type","volume":"6","author":"Yen","year":"2015","journal-title":"Nat. Commun."},{"key":"ref_3","first-page":"527","article-title":"Transcript Normalization and Segmentation of Tiling Array Data","volume":"13","author":"Zeller","year":"2008","journal-title":"Pac. Symp. Biocomput."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"457","DOI":"10.1093\/bioinformatics\/btr687","article-title":"Identifying small interfering RNA loci from high-throughput sequencing data","volume":"28","author":"Hardcastle","year":"2012","journal-title":"Bioinformatics"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Bischler, T., Kopf, M., and Vo\u00df, B. (2014). Transcript mapping based on dRNA-seq data. BMC Bioinform., 15.","DOI":"10.1186\/1471-2105-15-122"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"5320","DOI":"10.1073\/pnas.0601091103","article-title":"A high-resolution map of transcription in the yeast genome","volume":"103","author":"David","year":"2006","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1089\/cmb.2010.0267","article-title":"Discovering regulatory overlapping RNA transcripts","volume":"18","author":"Danford","year":"2011","journal-title":"J. Comput. Biol."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"142","DOI":"10.1214\/ss\/1028905933","article-title":"Statistical methods for DNA sequence segmentation","volume":"13","author":"Braun","year":"1998","journal-title":"Stat. Sci."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"1015","DOI":"10.1093\/molbev\/msp307","article-title":"Comparative Testing of DNA Segmentation Algorithms Using Benchmark Simulations","volume":"27","author":"Elhaik","year":"2010","journal-title":"Mol. Biol. Evol."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Girimurugan, S.B., Liu, Y., Lung, P.Y., Vera, D.L., Dennis, J.H., Bass, H.W., and Zhang, J. (2018). iSeg: An efficient algorithm for segmentation of genomic and epigenomic data. BMC Bioinform., 19.","DOI":"10.1186\/s12859-018-2140-3"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"12355","DOI":"10.1038\/s41598-017-12401-8","article-title":"Similarity-Based Segmentation of Multi-Dimensional Signals","volume":"7","author":"Murray","year":"2017","journal-title":"Sci. Rep."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"1793","DOI":"10.1093\/bioinformatics\/btt300","article-title":"A method for finding consensus breakpoints in the cancer genome from copy number data","volume":"29","author":"Halachev","year":"2013","journal-title":"Bioinformatics"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1198\/016214502753479239","article-title":"Clustering of Translocation Breakpoints","volume":"97","author":"Segal","year":"2002","journal-title":"J. Am. Stat. Assoc."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"846","DOI":"10.1080\/01621459.1971.10482356","article-title":"Objective criteria for the evaluation of clustering methods","volume":"66","author":"Rand","year":"1971","journal-title":"J. Am. Stat. Assoc."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"553","DOI":"10.1080\/01621459.1983.10478008","article-title":"A method for comparing two hierarchical clusterings","volume":"78","author":"Fowlkes","year":"1983","journal-title":"J. Am. Stat. Assoc."},{"key":"ref_16","first-page":"6","article-title":"A stability based method for discovering structure in clustered data","volume":"7","author":"Elisseeff","year":"2002","journal-title":"Pac. Symp. Biocomput."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1007\/BF01908075","article-title":"Comparing partitions","volume":"2","author":"Hubert","year":"1985","journal-title":"J. Classif."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Mirkin, B. (1996). Mathematical Classification and Clustering, Kluwer Academic Press.","DOI":"10.1007\/978-1-4613-0457-9"},{"key":"ref_19","unstructured":"Van Dongen, S. (2000). Performance Criteria for Graph Clustering and Markov Cluster Experiments, Centrum voor Wiskunde en Informatica. Technical Report."},{"key":"ref_20","unstructured":"Blalock, H.M., Aganbegian, A., Borodkin, F.M., Boudon, R., and Capecchi, V. (1975). On the Problem of Reconciling Partitions. Quantitative Sociology: International Perspectives on Mathematical and Statistical Modeling, Academic Press."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1090\/dimacs\/019\/01","article-title":"The median procedure for partitions","volume":"Volume 19","author":"Cox","year":"1995","journal-title":"Partitioning Data Sets"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1007\/BF00289116","article-title":"NP-hard problems in hierarchical-tree clustering","volume":"23","year":"1986","journal-title":"Acta Inform."},{"key":"ref_23","first-page":"323","article-title":"The complexity of computing medians of relations","volume":"3","author":"Wakabayashi","year":"1998","journal-title":"Resenhas IME-USP"},{"key":"ref_24","unstructured":"Eliassi-Rad, T., Ungar, L., Craven, M., and Gunopulos, D. (2006). Aggregating Time Partitions. Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Association for Computing Machinery."},{"key":"ref_25","unstructured":"De Raedt, L., and Wrobel, S. (2005). Comparing Clusterings: An Axiomatic View. Machine Learning, Proceedings of the Twenty-Second International Conference, Association for Computing Machinery."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1007\/978-3-540-45167-9_14","article-title":"Comparing clusterings by the variation of information","volume":"Volume 2777","author":"Warmuth","year":"2003","journal-title":"Learning Theory and Kernel Machines"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"8777","DOI":"10.1073\/pnas.90.19.8777","article-title":"Weighting in sequence space: A comparison of methods in terms of generlized sequences","volume":"90","author":"Vingron","year":"1993","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1145\/366573.366611","article-title":"On the approximation of curves by line segments using dynamic programming","volume":"4","author":"Bellman","year":"1961","journal-title":"Commun. ACM"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1002\/jae.659","article-title":"Computation and analysis of multiple structural change models","volume":"18","author":"Bai","year":"2002","journal-title":"J. Appl. Econom."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1023\/B:JIIS.0000039534.65423.00","article-title":"A Dynamic Programming Algorithm for Linear Text Segmentation","volume":"23","author":"Fragkou","year":"2004","journal-title":"J. Intell. Inf. Syst."},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Picard, F., Robin, S., Lavielle, M., Vaisse, C., and Daudin, J. (2005). A statistical approach for CGH microarray data analysis. BMC Bioinform., 6.","DOI":"10.1186\/1471-2105-6-27"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"1963","DOI":"10.1093\/bioinformatics\/btl289","article-title":"Transcript mapping with high-density oligonucleotide tiling arrays","volume":"22","author":"Huber","year":"2006","journal-title":"Bioinformatics"},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Terzi, E. (2006). Problems and Algorithms for Sequence Segmentations. [Ph.D. Thesis, Department of Computer Science Series of Publications A Report A-2006-5, University of Helsinki].","DOI":"10.1137\/1.9781611972764.28"},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Haiminen, N.H., Mannila, H., and Terzi, E. (2007). Comparing segmentations by applying randomization techniques. BMC Bioinform., 8.","DOI":"10.1186\/1471-2105-8-171"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"571","DOI":"10.1038\/nature02538","article-title":"Intergenic transcription is required to repress the Saccharomyces cerevisiae SER3 gene","volume":"429","author":"Martens","year":"2004","journal-title":"Nature"},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"1033","DOI":"10.1038\/nature07728","article-title":"Bidirectional promoters generate pervasive transcription in yeast","volume":"457","author":"Xu","year":"2009","journal-title":"Nature"},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1038\/nature12121","article-title":"Extensive transcriptional heterogeneity revealed by isoform profiling","volume":"497","author":"Pelechano","year":"2013","journal-title":"Nature"},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Parker, S., Fraczek, M.G., Wu, J., Shamsah, S., Manousaki, A., Dungrattanalert, K., de Almeida, R.A., Invernizzi, E., Burgis, T., and Omara, W. (2018). Large-scale profiling of noncoding RNA function in yeast. PLoS Genet., 14.","DOI":"10.1371\/journal.pgen.1007253"},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"7319","DOI":"10.1007\/s00253-018-9187-y","article-title":"A current view on long noncoding RNAs in yeast and filamentous fungi","volume":"102","author":"Till","year":"2018","journal-title":"Appl. Microbiol. Biotech."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"232","DOI":"10.1093\/molbev\/mst187","article-title":"Growth Rates Made Easy","volume":"31","author":"Hall","year":"2014","journal-title":"Mol. Biol. Evol."},{"key":"ref_41","doi-asserted-by":"crossref","unstructured":"Machn\u00e9, R., and Stadler, P.F. (2020, December 01). dpseg: Piecewise Linear Segmentation by Dynamic Programming. R Package Version 0.1.2. Available online: https:\/\/cran.r-project.org\/web\/packages\/dpseg\/.","DOI":"10.32614\/CRAN.package.dpseg"},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"600","DOI":"10.1093\/bib\/bbu026","article-title":"Performance evaluation of DNA copy number segmentation methods","volume":"16","author":"Rigaill","year":"2015","journal-title":"Brief. Bioinform."}],"container-title":["Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2079-3197\/9\/2\/17\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T05:20:27Z","timestamp":1760160027000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2079-3197\/9\/2\/17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,5]]},"references-count":42,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2021,2]]}},"alternative-id":["computation9020017"],"URL":"https:\/\/doi.org\/10.3390\/computation9020017","relation":{},"ISSN":["2079-3197"],"issn-type":[{"type":"electronic","value":"2079-3197"}],"subject":[],"published":{"date-parts":[[2021,2,5]]}}}