Alexandru I. Tomescu - Software

1. De Bruijn graphs and kmer sets GGCAT: Extremely-fast construction and querying of compacted and colored de Bruijn graphs matchtigs & eulertigs: Minimum plain-text representation of kmer sets / spectrum preserving string sets Accompanying papers: @article{Cracco:2023ab, author = {Andrea Cracco and Alexandru I. Tomescu}, date-added = {2023-05-31 11:59:56 +0300}, date-modified = {2023-05-31 12:01:58 +0300}, journal = {Genome Research}, note = {Short abstract at RECOMB 2023}, pages = {1198--1207}, title = {{Extremely fast construction and querying of compacted and colored de Bruijn graphs with GGCAT}}, url = {https://doi.org/10.1101/gr.277615.122}, volume = {33}, year = {2023}, bdsk-url-1 = {https://doi.org/10.1101/gr.277615.122}} @article{Schmidt2021.12.15.472871, abstract = {Kmer-based methods are widely used in bioinformatics, which raises the question of what is the smallest practically usable representation (i.e. plain text) of a set of kmers. We propose a polynomial algorithm computing a minimum such representation (which was previously posed as a potentially NP-hard open problem), as well as an efficient near-minimum greedy heuristic. When compressing genomes of large model organisms, read sets thereof or bacterial pangenomes, with only a minor runtime increase, we decrease the size of the representation by up to 60\% over unitigs and 27\% over previous work. Additionally, the number of strings is decreased by up to 97\% over unitigs and 91\% over previous work. Finally we show that a small representation has advantages in downstream applications, as it speeds up queries on the popular kmer indexing tool Bifrost by 1.66{\texttimes} over unitigs and 1.29{\texttimes} over previous work.Availability https://github.com/algbio/matchtigsCompeting Interest StatementThe authors have declared no competing interest.}, author = {Sebastian Schmidt and Shahbaz Khan and Jarno Alanko and Giulio E. Pibiri and Alexandru I. Tomescu}, date-added = {2023-06-13 10:13:32 +0300}, date-modified = {2023-06-13 10:17:50 +0300}, journal = {Genome Biology}, note = {Selected for talk at ISMB 2022}, pages = {136}, title = {Matchtigs: minimum plain text representation of kmer sets}, url = {https://doi.org/10.1186/s13059-023-02968-z}, volume = {24}, year = {2023}, bdsk-url-1 = {https://www.biorxiv.org/content/early/2022/02/09/2021.12.15.472871}, bdsk-url-2 = {https://doi.org/10.1101/2021.12.15.472871}} @inproceedings{DBLP:conf/wabi/SchmidtA22, author = {Sebastian Schmidt and Jarno Alanko}, title = {Eulertigs: Minimum Plain Text Representation of k-mer Sets Without Repetitions in Linear Time}, booktitle = {WABI 2022 - 22nd International Workshop on Algorithms in Bioinformatics}, series = {LIPIcs}, volume = {242}, pages = {2:1--2:21}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik}, year = {2022}, url = {https://doi.org/10.4230/LIPIcs.WABI.2022.2}, doi = {10.4230/LIPICS.WABI.2022.2}, timestamp = {Mon, 26 Sep 2022 17:09:13 +0200}, biburl = {https://dblp.org/rec/conf/wabi/SchmidtA22.bib}, bibsource = {dblp computer science bibliography, https://dblp.org}, note = {<strong>Best Paper Award</strong>} }

2. Fast solvers for flow decomposition problems via Integer Linear Programming Minimum Flow Decomposition in DAGs: An optimized solver for the Minimum Flow Decomposition problem in DAGs (and its variants with inexact flows and subpath constraints) Minimum Flow Decomposition in graphs with cycles: A solver for flow decompositions into paths and cycles, trails, or walks in general graphs with cycles MFD-safety: An implementation to compute safe paths for minimum flow decompositions Min-Path Error Flow Decompositions: A solver for flow decompositions of min-path error Accompanying papers: @inproceedings{Dias:2022uv, author = {Fernando H. C. Dias and Lucia Williams and Brendan Mumey and Alexandru I. Tomescu}, bibsource = {dblp computer science bibliography, https://dblp.org}, biburl = {https://dblp.org/rec/conf/recomb/DiasWMT22.bib}, booktitle = {RECOMB 2022 - 26th Annual International Conference on Research in Computational Molecular Biology}, date-added = {2022-05-23 11:03:33 +0300}, date-modified = {2022-06-16 15:25:10 +0300}, doi = {10.1007/978-3-031-04749-7_14}, pages = {230--245}, preprint = {https://arxiv.org/abs/2201.10923}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, timestamp = {Wed, 18 May 2022 18:07:47 +0200}, title = {{Fast, Flexible, and Exact Minimum Flow Decompositions via ILP}}, url = {https://doi.org/10.1007/978-3-031-04749-7_14}, volume = {13278}, year = {2022}, bdsk-url-1 = {https://doi.org/10.1007/978-3-031-04749-7%5C_14}} @inproceedings{grigorjew2023accelerating, author = {Andreas Grigorjew and Fernando H. C. Dias and Andrea Cracco and Romeo Rizzi and Alexandru I. Tomescu}, booktitle = {SEA 2024 - Symposium on Experimental Algorithms}, title = {Accelerating ILP solvers for Minimum Flow Decompositions through search space and dimensionality reductions}, url = {https://arxiv.org/abs/2311.10563}, year = {2024}, note = {To appear}} @article{safety-framework, author = {Fernando H. C. Dias and Manuel C{\'a}ceres and Lucia Williams and Brendan Mumey and Alexandru I. Tomescu}, date-added = {2023-11-07 09:32:30 +0200}, date-modified = {2023-11-07 09:32:30 +0200}, doi = {10.1093/bioinformatics/btad640}, journal = {Bioinformatics}, number = {11}, pages = {btad640}, title = {A Safety Framework for Flow Decomposition Problems via Integer Linear Programming}, url = {https://doi.org/10.1093/bioinformatics/btad640}, volume = {39}, year = {2023}, bdsk-url-1 = {https://doi.org/10.1093/bioinformatics/btad640}} @article{Dias2023.03.20.533019, abstract = {Minimum flow decomposition (MFD) is a common problem across various fields of Computer Science, where a flow is decomposed into a minimum set of weighted paths. However, in Bioinformatics applications, such as RNA transcript or quasi-species assembly, the flow is erroneous, since is obtained from noisy read coverages. Typical generalizations of the MFD problem to handle errors are based on least-squares formulations, or on modeling the erroneous flow values as ranges. All of these are thus focused on error-handling at the level of individual edges.Interpreting the flow decomposition problem as a robust optimization problem, we lift error-handling from individual edges to solution paths. As such, we introduce a new minimum path-error flow decomposition problem, for which we give an efficient Integer Linear Programming formulation. Our experimental results reveal that our formulation can account for errors with an accuracy significantly surpassing that of previous error-handling formulations, with computational requirements that remain practical.Competing Interest StatementThe authors have declared no competing interest.}, author = {Fernando H. C. Dias and Alexandru I. Tomescu}, date-added = {2023-04-10 10:50:33 +0300}, date-modified = {2023-04-10 10:51:06 +0300}, journal = {bioRxiv}, title = {Accurate Flow Decomposition via Robust Integer Linear Programming}, url = {https://doi.org/10.1101/2023.03.20.533019}, year = {2023}, bdsk-url-1 = {https://www.biorxiv.org/content/early/2023/03/23/2023.03.20.533019}, bdsk-url-2 = {https://doi.org/10.1101/2023.03.20.533019}} @article{Dias:2022aa, author = {Fernando H. C. Dias and Lucia Williams and Brendan Mumey and Alexandru I. Tomescu}, date-added = {2022-03-18 10:53:45 +0200}, date-modified = {2022-09-19 14:30:28 +0300}, journal = {arXiv}, title = {Minimum Flow Decomposition in Graphs with Cycles using Integer Linear Programming}, url = {https://arxiv.org/abs/2209.00042}, volume = {abs/2209.00042}, year = {2022}, bdsk-url-1 = {https://arxiv.org/abs/2011.12635}}

3. Alignment to pangenomes GraphChainer: An accurate aligner of long reads to a variation graph, based on co-linear chaining Performance Minimum Path Cover: C++ implementations of different fast algorithms for Minimum Path Cover Accompanying papers: @article{Ma2022.01.07.475257, abstract = {Aligning reads to a variation graph is a standard task in pangenomics, with downstream applications in e.g., improving variant calling. While the vg toolkit (Garrison et al., Nature Biotechnology, 2018) is a popular aligner of short reads, GraphAligner (Rautiainen and Marschall, Genome Biology, 2020) is the state-of-the-art aligner of long reads. GraphAligner works by finding candidate read occurrences based on individually extending the best seeds of the read in the variation graph. However, a more principled approach recognized in the community is to co-linearly chain multiple seeds. We present a new algorithm to co-linearly chain a set of seeds in an acyclic variation graph, together with the first efficient implementation of such a co-linear chaining algorithm into a new aligner of long reads to variation graphs, GraphChainer. Compared to GraphAligner, at a normalized edit distance threshold of 40\%, it aligns 9\% to 12\% more reads, and 15\% to 19\% more total read length, on real PacBio reads from human chromosomes 1 and 22. On both simulated and real data, GraphChainer aligns between 97\% and 99\% of all reads, and of total read length. At the more stringent normalized edit distance threshold of 30\%, GraphChainer aligns up to 29\% more total real read length than GraphAligner.GraphChainer is freely available at https://github.com/algbio/GraphChainerCompeting Interest StatementThe authors have declared no competing interest.}, author = {Jun Ma and Manuel C{\'a}ceres and Leena Salmela and Veli M{\"a}kinen and Alexandru I. Tomescu}, date-added = {2023-08-25 12:05:10 +0300}, date-modified = {2023-10-31 08:56:13 +0200}, journal = {Bioinformatics}, number = {8}, pages = {btad460}, title = {Chaining for accurate alignment of erroneous long reads to acyclic variation graphs}, url = {https://doi.org/10.1093/bioinformatics/btad460}, volume = {39}, year = {2023}, bdsk-url-1 = {https://www.biorxiv.org/content/early/2022/01/07/2022.01.07.475257}, bdsk-url-2 = {https://doi.org/10.1101/2022.01.07.475257}} @inproceedings{DBLP:journals/corr/abs-2308-08960, author = {Manuel C{\'a}ceres and Brendan Mumey and Santeri Toivonen and Alexandru I. Tomescu}, title = {Practical Minimum Path Cover}, booktitle = {SEA 2024 - Symposium on Experimental Algorithms}, year = {2024}, url = {https://doi.org/10.48550/arXiv.2308.08960}, note = {To appear} } @inproceedings{Caceres:2021wi, author = {Manuel C{\'a}ceres and Massimo Cairo and Brendan Mumey and Romeo Rizzi and Alexandru I. Tomescu}, booktitle = {SODA 2022 - ACM-SIAM Symposium on Discrete Algorithms}, date-added = {2022-01-14 14:05:03 +0200}, date-modified = {2022-01-17 09:28:12 +0200}, doi = {10.1137/1.9781611977073.18}, pages = {359-376}, preprint = {https://arxiv.org/abs/2107.05717}, title = {Sparsifying, Shrinking and Splicing for Minimum Path Cover in Parameterized Linear Time}, url = {https://epubs.siam.org/doi/abs/10.1137/1.9781611977073.18}, year = {2022}, bdsk-url-1 = {https://epubs.siam.org/doi/abs/10.1137/1.9781611977073.18}, bdsk-url-2 = {https://doi.org/10.1137/1.9781611977073.18}} @article{Equi:2023aa, author = {Massimo Equi and Veli M{\"a}kinen and Alexandru I. Tomescu and Roberto Grossi}, date-added = {2023-04-20 05:55:06 +0300}, date-modified = {2023-04-20 05:55:28 +0300}, journal = {ACM Transactions on Algorithms}, number = {3}, pages = {1--25}, title = {On the Complexity of String Matching for Graphs}, url = {https://doi.org/10.1145/3588334}, volume = {19}, year = {2023}, bdsk-url-1 = {https://doi.org/10.1145/3588334}} @article{EQUI2023114128, abstract = {The string matching problem on a node-labeled graph G=(V,E) asks whether a given pattern string P equals the concatenation of node labels of some path in G. This is a basic primitive in various problems in bioinformatics, graph databases, or networks, recently proven to have a O(|E||P|)-time lower bound, under the Orthogonal Vectors Hypothesis (OVH) (Equi et al. (2019) [11]). We consider its indexed version, where the graph is indexed to support string queries. We show that, under OVH, no polynomial-time index of the graph performed in time O(|E|α) can support querying P in time O(|P|+|E|δ|P|β), with either δ<1 or β<1. We present our techniques as a general framework, introducing the notion of linear independent-components (lic) reduction, from which we derive our result. This allow us to also translate the quadratic conditional lower bound of Backurs and Indyk (2015) [47] for the problem of matching a query string inside a text, under edit distance, into an analogous tight quadratic lower bound for its indexed version. This improves the recent result of Cohen-Addad, Feuilloley and Starikovskaya (2019) [48], with a slightly different boundary condition. We also apply our technique to obtain the first quadratic indexing lower bounds for Fr{\'e}chet distance and rooted unlabeled subtree-isomorphism queries.}, author = {Massimo Equi and Veli Mäkinen and Alexandru I. Tomescu}, date-added = {2023-08-25 18:01:43 +0300}, date-modified = {2023-08-25 18:01:43 +0300}, issn = {0304-3975}, journal = {Theoretical Computer Science}, keywords = {Exact pattern matching, Indexing, Orthogonal vectors, Complexity theory, Reductions, Lower bounds, Edit distance, Graph query, Fr{\'e}chet distance, Subtree isomorphism}, number = {9}, pages = {114128}, title = {Graphs Cannot be Indexed in Polynomial Time for Sub-quadratic Time String Matching, unless SETH Fails}, url = {https://doi.org/10.1016/j.tcs.2023.114128}, volume = {975}, year = {2023}, bdsk-url-1 = {https://www.sciencedirect.com/science/article/pii/S0304397523004413}, bdsk-url-2 = {https://doi.org/10.1016/j.tcs.2023.114128}}

4. Super-unitigs for genome assembly Y-to-V contigs and omnitigs: An assembler of Y-to-V contigs and omnitigs Practical omnitigs: A repository to conduct experiments with omnitig-related models in the context of genome assembly Genome graph: A Rust crate to represent genome graphs (supports mainly bigraphs at the moment) Accompanying papers: @article{Schmidt2023.01.30.526175, abstract = {Despite the long history of genome assembly research, there remains a large gap between the theoretical and practical work. There is practical software with little theoretical underpinning of accuracy on one hand and theoretical algorithms which have not been adopted in practice on the other. In this paper we attempt to bridge the gap between theory and practice by showing how the theoretical safe-and-complete framework can be integrated into existing assemblers in order to improve contiguity. The optimal algorithm in this framework, called the omnitig algorithm, has not been used in practice due to its complexity and its lack of robustness to real data. Instead, we pursue a simplified notion of omnitigs, giving an efficient algorithm to compute them and demonstrating their safety under certain conditions. We modify two assemblers (wtdbg2 and Flye) by replacing their unitig algorithm with the simple omnitig algorithm. We test our modifications using real HiFi data from the Drosophilia melanogaster and the Caenorhabditis elegans genome. Our modified algorithms lead to a substantial improvement in alignment-based contiguity, with negligible computational costs and either no or a small increase in the number of misassemblies.Competing Interest StatementThe authors have declared no competing interest.}, author = {Schmidt, Sebastian and Toivonen, Santeri and Medvedev, Paul and Tomescu, Alexandru I.}, date-added = {2023-02-09 06:42:17 +0200}, date-modified = {2023-02-09 06:42:37 +0200}, doi = {10.1101/2023.01.30.526175}, elocation-id = {2023.01.30.526175}, eprint = {https://www.biorxiv.org/content/10.1101/2023.01.30.526175v1}, journal = {bioRxiv}, publisher = {Cold Spring Harbor Laboratory}, title = {The omnitig framework can improve genome assembly contiguity in practice}, url = {https://www.biorxiv.org/content/10.1101/2023.01.30.526175v1}, year = {2023}, bdsk-url-1 = {https://www.biorxiv.org/content/early/2023/02/02/2023.01.30.526175}, bdsk-url-2 = {https://doi.org/10.1101/2023.01.30.526175}} @article{flowtigs, abstract = {A decomposition of a network flow is a set of weighted paths whose superposition equals the flow. The problem of characterising and computing safe walks for flow decompositions has so far seen only a partial solution by restricting the flow decomposition to consist of paths, and the graph to be directed and acyclic (DAG). However, the problem of decomposing into closed walks in a general graph (allowing cycles) is still open. In this paper, we give a simple and linear-time-verifiable complete characterisation (flowtigs) of walks that are safe in such general flow decompositions, i.e. that are subwalks of any possible flow decomposition. Our characterisation generalises over the previous one for DAGs, using a more involved proof of correctness that works around various issues introduced by cycles. We additionally provide an optimal O(mn)-time algorithm that identifies all maximal flowtigs and represents them inside a compact structure. We also implement this algorithm and show that it is very fast in practice. On the practical side, we study flowtigs in the use-case of metagenomic assembly. By using the abundances of the metagenomic assembly graph as flow values, we can model the possible assembly solutions as flow decompositions into closed walks. Compared to reporting unitigs or maximal safe walks based only on the graph structure (structural contigs), reporting flowtigs results in a notably more contiguous assembly. Specifically, on shorter contigs (75-percentile), we get an improvement in assembly contiguity of up to 100\% over unitigs, and up to 61.9\% over structural contigs. For the 50-percentile of contiguity we get an improvement of up to 17.0\% over unitigs and up to 14.6\% over structural contigs. These improvements are more pronounced the more complex the assembly graphs are, and the improvements of flowtigs over unitigs are multiple times larger compared to the improvements of previous safe walks over unitigs.Competing Interest StatementThe authors have declared no competing interest.}, author = {Francisco Sena and Eliel Ingervo and Shahbaz Khan and Andrey Prjibelski and Sebastian Schmidt and Alexandru I. Tomescu}, date-added = {2023-11-21 09:32:21 +0200}, date-modified = {2023-11-21 09:32:21 +0200}, doi = {10.1101/2023.11.17.567499}, elocation-id = {2023.11.17.567499}, eprint = {https://www.biorxiv.org/content/early/2023/11/20/2023.11.17.567499.full.pdf}, journal = {bioRxiv}, publisher = {Cold Spring Harbor Laboratory}, title = {Flowtigs: Safety in flow decompositions for assembly graphs}, url = {https://doi.org/10.1101/2023.11.17.567499}, year = {2023}, bdsk-url-1 = {https://www.biorxiv.org/content/early/2023/11/20/2023.11.17.567499}, bdsk-url-2 = {https://doi.org/10.1101/2023.11.17.567499}} @conference{Cairo:2022aa, author = {Massimo Cairo and Shahbaz Khan and Romeo Rizzi and Sebastian Schmidt and Alexandru I. Tomescu and Elia C. Zirondelli}, booktitle = {STACS 2023 - 40th International Symposium on Theoretical Aspects of Computer Science}, copyright = {Creative Commons Attribution 4.0 International}, date-added = {2023-03-22 09:26:31 +0200}, date-modified = {2023-03-22 09:28:01 +0200}, pages = {17:1--17:17}, preprint = {https://arxiv.org/abs/2210.07530}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik}, series = {LIPIcs}, title = {Cut paths and their remainder structure, with applications}, url = {https://doi.org/10.4230/LIPIcs.STACS.2023.17}, volume = {254}, year = {2023}, bdsk-url-1 = {https://arxiv.org/abs/2210.07530}, bdsk-url-2 = {https://doi.org/10.48550/ARXIV.2210.07530}} @article{Cairo:2019:OON:3351875.3341731, Acmid = {3341731}, Address = {New York, NY, USA}, Articleno = {48}, Author = {Cairo, Massimo and Medvedev, Paul and Acosta, Nidia Obscura and Rizzi, Romeo and Tomescu, Alexandru I.}, Date-Added = {2019-08-05 09:23:48 +0300}, Date-Modified = {2019-08-05 09:23:59 +0300}, Doi = {10.1145/3341731}, Issn = {1549-6325}, Issue_Date = {July 2019}, Journal = {ACM Transactions on Algorithms}, Keywords = {Genome assembly, edge-covering walk, graph algorithm, safe and complete algorithm, strong bridge}, Month = jul, Number = {4}, Numpages = {17}, Pages = {48:1--48:17}, Publisher = {ACM}, Title = {An Optimal O(nm) Algorithm for Enumerating All Walks Common to All Closed Edge-covering Walks of a Graph}, Url = {http://doi.acm.org/10.1145/3341731}, Volume = {15}, Year = {2019}, Bdsk-Url-1 = {http://doi.acm.org/10.1145/3341731}, Bdsk-Url-2 = {https://doi.org/10.1145/3341731}} @inproceedings{Tomescu:aa, Altmetric = {<span data-badge-popover='right' data-badge-type='2' data-altmetric-id='4985838' data-hide-no-mentions='true' data-hide-less-than='2' class='altmetric-embed' style="position: relative; top: 4px;"></span>}, Author = {Alexandru I. Tomescu and Paul Medvedev}, Booktitle = {RECOMB 2016 - 20th Annual International Conference on Research in Computational Molecular Biology}, Date-Added = {2016-04-27 12:44:09 +0000}, Date-Modified = {2016-04-27 12:44:09 +0000}, Extended_Version = {http://arxiv.org/abs/1601.02932}, Implementation = {https://github.com/alexandrutomescu/complete-contigs}, Pages = {152-163}, Publisher = {Springer-Verlag}, Series = {Lecture Notes in Computer Science}, Title = {Safe and complete contig assembly via omnitigs}, Url = {http://dx.doi.org/10.1007/978-3-319-31957-5_11}, Volume = {9649}, Year = {2016}, Bdsk-Url-1 = {http://dx.doi.org/10.1007/978-3-319-31957-5}}

5. Protein and RNA alignment EMERALD: Safety windows in protein alignments by exploring the suboptimal alignment space rna-safe-complete: Safe and Complete RNA Secondary Structure Prediction for the maximum base pairs model Accompanying papers: @article{Grigorjew2023.01.11.523286, abstract = {Sequence alignments have become the foundation of life science research by unlocking biological mechanisms through protein comparisons. Despite its methodological success, most algorithmic innovation in the past decades focused on the optimal alignment problem, while often ignoring information derived from suboptimal solutions. The assumption that the score-derived optimal alignment represents the biologically most relevant choice has led many life scientists to accept this reduced dimension from thousands or millions of possible alignment configurations to one optimal alignment setting. However, we argue that one optimal alignment per pairwise sequence comparison may have been a reasonable approximation when dealing with very similar sequences, but is insufficient when aiming to capture the natural variation of the protein universe at tree-of-life scale. To overcome this alignment-sensitivity limitation, we propose the concept of pairwise alignment-safety as a way to explore the neighborhood of suboptimal alignment configurations when comparing divergent protein sequences. We show that by using alignment-safe intervals, it is possible to encode the defining structural features of proteins even when comparing highly divergent sequences. To demonstrate this, we present EMERALD, a dedicated command line tool able to infer alignment-safe sequence intervals from biodiverse protein sequence clusters. EMERALD effectively explores suboptimal alignment paths within the pairwise dynamic programming matrix and flags robust intervals that are shared across all suboptimal configurations. We apply EMERALD to clusters of 396k sequences generated from the Swiss-Prot database and show that alignment-safe intervals derived from the suboptimal alignment space are sufficient to capture the structural identity of biodiverse proteins even when comparing highly divergent clusters.Competing Interest StatementThe authors have declared no competing interest.}, author = {Andreas Grigorjew and Artur Gynter and Fernando Dias and Benjamin Buchfink and Hajk-Georg Drost* and Alexandru I. Tomescu*}, date-added = {2023-08-02 12:51:47 +0300}, date-modified = {2023-08-02 14:02:42 +0300}, journal = {Genome Biology}, note = {*Equal contribution. Selected for talk at ISMB 2023}, pages = {168}, title = {Sensitive inference of alignment-safe intervals from biodiverse protein sequence clusters using EMERALD}, url = {https://doi.org/10.1186/s13059-023-03008-6}, volume = {24}, year = {2023}, bdsk-url-1 = {https://www.biorxiv.org/content/early/2023/01/15/2023.01.11.523286}, bdsk-url-2 = {https://doi.org/10.1101/2023.01.11.523286}} @inproceedings{DBLP:conf/cpm/KiiralaST19, Author = {Niko Kiirala and Leena Salmela and Alexandru I. Tomescu}, Bibsource = {dblp computer science bibliography, https://dblp.org}, Biburl = {https://dblp.org/rec/bib/conf/cpm/KiiralaST19}, Booktitle = {CPM 2019 - 30th Annual Symposium on Combinatorial Pattern Matching}, Crossref = {DBLP:conf/cpm/2019}, Date-Added = {2019-06-19 17:52:56 +0300}, Date-Modified = {2019-06-19 17:53:54 +0300}, Doi = {10.4230/LIPIcs.CPM.2019.8}, Pages = {8:1--8:16}, Series = {LIPIcs}, Timestamp = {Fri, 07 Jun 2019 09:03:47 +0200}, Title = {Safe and Complete Algorithms for Dynamic Programming Problems, with an Application to {RNA} Folding}, Url = {https://doi.org/10.4230/LIPIcs.CPM.2019.8}, Volume = {128}, Year = {2019}, Bdsk-Url-1 = {https://doi.org/10.4230/LIPIcs.CPM.2019.8}}

6. Inferring tumor phylogenies

• MIPUP: Minimum unmixed perfect phylogenies via branchings in graphs and ILP
• SNV-PPILP: Refined SNV calling for tumor data using perfect phylogenies and ILP