Alexandru I. Tomescu - Software

Homepage • Publications • Software • Teaching and Supervision

Below are some bioinformatics software projects develped in my team

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 = {Best Paper Award}
 }

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 - 22nd International Symposium on Experimental Algorithms},
 date-added = {2024-03-28 10:02:17 +0200},
 date-modified = {2024-03-28 10:03:00 +0200},
 note = {Runner-up for the Best Paper Award at SEA 2024 (i.e. 2nd place)},
 pages = {14:1--14:19},
 publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
 series = {Leibniz International Proceedings in Informatics (LIPIcs)},
 title = {Accelerating ILP solvers for Minimum Flow Decompositions through search space and dimensionality reductions},
 url = {https://doi.org/10.4230/LIPIcs.SEA.2024.14},
 volume = {301},
 year = {2024},
 bdsk-url-1 = {https://doi.org/10.4230/LIPIcs.SEA.2024.14}}

@misc{sena2024safepathssequencesscalable,
        title={Safe Paths and Sequences for Scalable ILPs in RNA Transcript Assembly Problems}, 
        author={Francisco Sena and Alexandru I. Tomescu},
        year={2024},
        journal = {arXiv},
        eprint={2411.03871},
        archivePrefix={arXiv},
        primaryClass={cs.DS},
        url={https://arxiv.org/abs/2411.03871}
      }

@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 = {IEEE/ACM Transactions on Computational Biology and Bioinformatics},
        note = {Available online},
        preprint = {https://researchportal.helsinki.fi/files/325850154/TCBB3433523.pdf},
        title = {Accurate Flow Decomposition via Robust Integer Linear Programming},
        url = {https://doi.org/10.1109/TCBB.2024.3433523},
        year = {2024},
        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{DBLP:journals/corr/abs-2308-08960,
      author = {Manuel C{\'a}ceres and Brendan Mumey and Santeri Toivonen and Alexandru I. Tomescu},
      booktitle = {SEA 2024 - 22nd International Symposium on Experimental Algorithms},
      date-added = {2024-03-28 10:03:58 +0200},
      date-modified = {2024-03-28 10:04:50 +0200},
      pages = {3:1--3:19},
      publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
      series = {Leibniz International Proceedings in Informatics (LIPIcs)},
      title = {Practical Minimum Path Cover},
      url = {https://doi.org/10.4230/LIPIcs.SEA.2024.3},
      volume = {301},
      year = {2024},
      bdsk-url-1 = {https://doi.org/10.4230/LIPIcs.SEA.2024.3}}

@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,
        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:

@inproceedings{schmidt_et_al:LIPIcs.WABI.2024.8,
    address = {Dagstuhl, Germany},
    author = {Sebastian Schmidt and Santeri Toivonen and Paul Medvedev* and Alexandru I. Tomescu*},
    booktitle = {WABI 2024 - 24th International Workshop on Algorithms in Bioinformatics},
    doi = {10.4230/LIPIcs.WABI.2024.8},
    editor = {Pissis, Solon P. and Sung, Wing-Kin},
    isbn = {978-3-95977-340-9},
    issn = {1868-8969},
    note = {*Equal contribution},
    pages = {8:1--8:16},
    publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
    series = {Leibniz International Proceedings in Informatics (LIPIcs)},
    title = {Applying the Safe-And-Complete Framework to Practical Genome Assembly},
    url = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2024.8},
    urn = {urn:nbn:de:0030-drops-206520},
    volume = {312},
    year = {2024},
    bdsk-url-1 = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2024.8},
    bdsk-url-2 = {https://doi.org/10.4230/LIPIcs.WABI.2024.8}}

@article{flowtigs,
      author = {Francisco Sena and Eliel Ingervo and Shahbaz Khan and Andrey Prjibelski and Sebastian Schmidt and Alexandru I. Tomescu},
      journal = {iScience},
      preprint = {https://doi.org/10.1101/2023.11.17.567499},
      publisher = {Cell Press},
      title = {Flowtigs: safety in flow decompositions for assembly graphs},
      url = {https://doi.org/10.1016/j.isci.2024.111208},
      year = {2024},
      volume = {27},
      number = {12},
      pages = {111208},
      bdsk-url-1 = {https://doi.org/10.1016/j.isci.2024.111208}}

@article{10.1145/3632176,
        abstract = {Genome assembly asks to reconstruct an unknown string from many shorter substrings of it. Even though it is one of the key problems in Bioinformatics, it is generally lacking major theoretical advances. Its hardness stems both from practical issues (size and errors of real data), and from the fact that problem formulations inherently admit multiple solutions. Given these, at their core, most state-of-the-art assemblers are based on finding non-branching paths (unitigs) in an assembly graph. While such paths constitute only partial assemblies, they are likely to be correct. More precisely, if one defines a genome assembly solution as a closed arc-covering walk of the graph, then unitigs appear in all solutions, being thus safe partial solutions. Until recently, it was open what are all the safe walks of an assembly graph. Tomescu and Medvedev (RECOMB 2016) characterized all such safe walks (omnitigs), thus giving the first safe and complete genome assembly algorithm. Even though maximal omnitig finding was later improved to quadratic time by Cairo et al. (ACM Trans. Algorithms 2019), it remained open whether the crucial linear-time feature of finding unitigs can be attained with omnitigs. We answer this question affirmatively, by describing a surprising O(m)-time algorithm to identify all maximal omnitigs of a graph with n nodes and m arcs, notwithstanding the existence of families of graphs with Θ(mn) total maximal omnitig size. This is based on the discovery of a family of walks (macrotigs) with the property that all the non-trivial omnitigs are univocal extensions of subwalks of a macrotig. This has two consequences: (1) A linear-time output-sensitive algorithm enumerating all maximal omnitigs. (2) A compact O(m) representation of all maximal omnitigs, which allows, e.g., for O(m)-time computation of various statistics on them. Our results close a long-standing theoretical question inspired by practical genome assemblers, originating with the use of unitigs in 1995. We envision our results to be at the core of a reverse transfer from theory to practical and complete genome assembly programs, as has been the case for other key Bioinformatics problems.},
        address = {New York, NY, USA},
        author = {Massimo Cairo and Romeo Rizzi and Alexandru I. Tomescu and Elia C. Zirondelli},
        date-added = {2023-12-11 15:07:29 +0200},
        date-modified = {2023-12-11 15:08:02 +0200},
        doi = {10.1145/3632176},
        issn = {1549-6325},
        journal = {ACM Transactions on Algorithms},
        keywords = {strong connectivity, Graph algorithm, reachability under failures},
        month = {dec},
        number = {1},
        pages = {1--26},
        publisher = {Association for Computing Machinery},
        title = {{Genome Assembly, from Practice to Theory: Safe, Complete and Linear-Time}},
        url = {https://doi.org/10.1145/3632176},
        volume = {20},
        year = {2023},
        bdsk-url-1 = {https://doi.org/10.1145/3632176},
        note = {Extended version of ICALP 2021 paper}}

@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 = {},
 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}}

safety in protein alignments via suboptimal alignments

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

Accompanying papers:

@article{doi:10.1093/bioinformatics/bty683,
    Author = {Edin Husi{\'c} and Xinyue Li and Ademir Hujdurovi{\'c} and Miika Mehine and Romeo Rizzi and Veli M{\"a}kinen and Martin Milani{\v c}* and Alexandru I. Tomescu*},
    Date-Added = {2019-03-04 13:50:00 +0200},
    Date-Modified = {2019-03-04 13:52:04 +0200},
    Doi = {10.1093/bioinformatics/bty683},
    Eprint = {/oup/backfile/content_public/journal/bioinformatics/pap/10.1093_bioinformatics_bty683/1/bty683.pdf},
    Journal = {Bioinformatics},
    Note = {*Equal contribution},
    Number = {5},
    Pages = {769-777},
    Title = {MIPUP: Minimum perfect unmixed phylogenies for multi-sampled tumors via branchings and ILP},
    Url = {http://dx.doi.org/10.1093/bioinformatics/bty683},
    Volume = {35},
    Year = {2019},
    Bdsk-Url-1 = {http://dx.doi.org/10.1093/bioinformatics/bty683}}
    
    @article{Rens:aa,
      Author = {Karen E. van Rens and Veli M{\"a}kinen and Alexandru I. Tomescu},
      Date-Modified = {2015-04-20 19:10:08 +0000},
      Doi = {10.1093/bioinformatics/btu755},
      Implementation = {http://www.cs.helsinki.fi/gsa/snv-ppilp/},
      Journal = {Bioinformatics},
      Number = {7},
      Pages = {1133-1135},
      Title = {SNV-PPILP: Refined SNV calling for tumor data using perfect phylogenies and ILP},
      Url = {http://bioinformatics.oxfordjournals.org/cgi/content/abstract/btu755?ijkey=XNg7zRpqjrCkRUI&keytype=ref},
      Volume = {31},
      Year = {2015},
      Bdsk-Url-1 = {http://bioinformatics.oxfordjournals.org/cgi/content/abstract/btu755?ijkey=XNg7zRpqjrCkRUI&keytype=ref},
      Bdsk-Url-2 = {http://dx.doi.org/10.1093/bioinformatics/btu755}}

(view) (view) (proof scenario) (slides) (preprint) (implementation) (extended version)

(),
, , ,
Supervisors: