Genome-scale Algorithmics research group / Veli Mäkinen

  • PL 68 (Gustaf Hällströmin katu 2b), B230

    HELSINGIN YLIOPISTO

    Finland

Publications

2020

Fast Indexes for Gapped Pattern Matching

Cáceres, M., Puglisi, S. & Zhukova, B., 17 Jan 2020, p. 493-504. 12 p.

Research output: Conference materialsPaper

Finding all maximal perfect haplotype blocks in linear time

Alanko, J., Bannai, H., Cazaux, B., Peterlongo, P. & Stoye, J., 10 Feb 2020, In : Algorithms for Molecular Biology. 15, 1, 7 p., 2.

Research output: Contribution to journalArticleScientificpeer-review

Open Access
File

Linear Time Construction of Indexable Founder Block Graphs

Mäkinen, V., Cazaux, B., Equi, M., Norri, T. & Tomescu, A., 25 Aug 2020, 20th International Workshop on Algorithms in Bioinformatics (WABI 2020). Kingsford, C. & Pisanti, N. (eds.). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, p. 1-18 18 p. 7. (Leibniz International Proceedings in Informatics; vol. 172).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Open Access
File

Regular Languages meet Prefix Sorting

Alanko, J., Prezza, N., Policriti, A. & D’Agostino, G., 2020, (Accepted/In press) Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2020.

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Scalable Reference Genome Assembly from Compressed Pan-Genome Index with Spark

Maarala, A. I., Arasalo, O., Valenzuela, D., Heljanko, K. & Mäkinen, V., 18 Sep 2020, Big Data -- BigData 2020. Nepal, S., Cao, W., Nasridinov, A., Bhuiyan, MD. Z. A., Guo, X. & Zhang, L-J. (eds.). Cham: Springer International Publishing, p. 68-84 17 p.

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Open Access

Tight Upper and Lower Bounds on Suffix Tree Breadth

Badkobeh, G., Gawrychowski, P., Kärkkäinen, J., Puglisi, S. & Zhukova, B., 23 Jan 2020, (Accepted/In press) In : Theoretical Computer Science.

Research output: Contribution to journalArticleScientificpeer-review

2019

A framework for space-efficient variable-order Markov models

Cunial, F., Alanko, J. & Belazzougui, D., 15 Nov 2019, In : Bioinformatics. 35, 22, p. 4607-4616 10 p.

Research output: Contribution to journalArticleScientificpeer-review

Aligning optical maps to de Bruijn graphs

Mukherjee, K., Alipanahi, B., Kahveci, T., Salmela, L. & Boucher, C., 15 Sep 2019, In : Bioinformatics. 35, 18, p. 3250-3256 7 p.

Research output: Contribution to journalArticleScientificpeer-review

Open Access
File

Applying the Positional Burrows–Wheeler Transform to All-Pairs Hamming distance

Mäkinen, V. & Norri, T., Jun 2019, In : Information Processing Letters. 146, p. 17-19 3 p.

Research output: Contribution to journalArticleScientificpeer-review

Open Access
File

Bit-parallel sequence-to-graph alignment

Rautiainen, M., Mäkinen, V. & Marschall, T., 1 Oct 2019, In : Bioinformatics. 35, 19, p. 3599-3607 9 p.

Research output: Contribution to journalArticleScientificpeer-review

Open Access
File

Comparison of LZ77-type parsings

Kosolobov, D. & Shur, A. M., Jan 2019, In : Information Processing Letters. 141, p. 25-29 5 p.

Research output: Contribution to journalArticleScientificpeer-review

Compressed multiple pattern matching

Kosolobov, D. & Sivukhin, N., 2019, 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019). Pisanti, N. & Pissis, S. P. (eds.). Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 14 p. 13. (Leibniz International Proceedings in Informatics (LIPIcs); vol. 128).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Open Access
File

Fixed Block Compression Boosting in FM-Indexes: Theory and Practice

Gog, S., Kärkkäinen, J., Kempa, D., Petri, M. & Puglisi, S. J., Apr 2019, In : Algorithmica. 81, 4, p. 1370-1391 22 p.

Research output: Contribution to journalArticleScientificpeer-review

File

Hardness of Covering Alignment: Phase Transition in Post-Sequence Genomics

Rizzi, R., Cairo, M., Mäkinen, V., Tomescu, A. I. & Valenzuela, D., Feb 2019, In : IEEE/ACM Transactions on Computational Biology and Bioinformatics. 16, 1, p. 23-30 8 p.

Research output: Contribution to journalArticleScientificpeer-review

Open Access
File

Kermit: Linkage map guided long read assembly

Walve, R., Rastas, P. & Salmela, L., 20 Mar 2019, In : Algorithms for Molecular Biology. 14, 1, 10 p., 8.

Research output: Contribution to journalArticleScientificpeer-review

Open Access
File

Linear Time Maximum Segmentation Problems in Column Stream Model

Cazaux, B., Kosolobov, D., Mäkinen, V. & Norri, T., 2019, String Processing and Information Retrieval : 26th International Symposium, {SPIRE} 2019, Segovia, Spain, October 7-9, 2019, Proceedings. Brisaboa, N. R. & Puglisi, S. J. (eds.). Cham: Springer Nature Switzerland, p. 322-336 15 p. (Lecture Notes in Computer Science; vol. 11811).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Linear time minimum segmentation enables scalable founder reconstruction

Norri, T., Cazaux, B., Kosolobov, D. & Mäkinen, V., 17 May 2019, In : Algorithms for Molecular Biology. 14, 15 p., 12.

Research output: Contribution to journalArticleScientificpeer-review

Open Access
File

MIPUP: minimum perfect unmixed phylogenies for multi-sampled tumors via branchings and ILP

Husic, E., Li, X., Hujdurovic, A., Mehine, M., Rizzi, R., Mäkinen, V., Milanic, M. & Tomescu, A. I., 1 Mar 2019, In : Bioinformatics. 35, 5, p. 769-777 9 p.

Research output: Contribution to journalArticleScientificpeer-review

Open Access
File

On Lempel-Ziv Decompression in Small Space

Puglisi, S. J. & Rossi, M., 2019, 2019 DATA COMPRESSION CONFERENCE (DCC). New York: IEEE, p. 221-230 10 p. (IEEE Data Compression Conference).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

On the Complexity of String Matching for Graphs

Equi, M., Grossi, R., Mäkinen, V. & Tomescu, A., 2019, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Baier, C., Chatzigiannakis, I., Flocchini, P. & Leonardi, S. (eds.). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, p. 55:1--55:15 15 p. (Leibniz International Proceedings in Informatics (LIPIcs); vol. 132).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Open Access
File

Safe and Complete Algorithms for Dynamic Programming Problems, with an Application to RNA Folding

Kiirala, N., Salmela, L. & Tomescu, A., 2019, 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019). Pisanti, N. & Pissis, S. P. (eds.). Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, p. 8:1-8:16 16 p. (Edit Leibniz International Proceedings in Informatics (LIPIcs); vol. 128).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Open Access
File

Safely Filling Gaps with Partial Solutions Common to All Solutions

Salmela, L. & Tomescu, A. I., 2019, In : IEEE/ACM Transactions on Computational Biology and Bioinformatics. 16, 2, p. 617-626 10 p.

Research output: Contribution to journalArticleScientificpeer-review

Open Access
File

Sparse Dynamic Programming on DAGs with Small Width

Mäkinen, V., Tomescu, A. I., Kuosmanen, A., Paavilainen, T., Gagie, T. & Chikhi, R., May 2019, In : ACM Transactions on Algorithms. 15, 2, 21 p., 29.

Research output: Contribution to journalArticleScientificpeer-review

Open Access
File

Tunneling on Wheeler Graphs

Alanko, J., Gagie, T., Navarro, G. & Benkner, L. S., 2019, 2019 DATA COMPRESSION CONFERENCE (DCC). New York: IEEE, p. 122-131 10 p. (IEEE Data Compression Conference).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Open Access
File
2018

A safe and complete algorithm for metagenomic assembly

Acosta, N. O., Mäkinen, V. & Tomescu, A. I., 7 Feb 2018, In : Algorithms for Molecular Biology. 13, 12 p., 3.

Research output: Contribution to journalArticleScientificpeer-review

Open Access
File

Bidirectional Variable-Order de Bruijn Graphs

Belazzougui, D., Gagie, T., Mäkinen, V., Previtali, M. & Puglisi, S. J., Dec 2018, In : International Journal of Foundations of Computer Science. 29, 8, p. 1279-1295 17 p.

Research output: Contribution to journalArticleScientificpeer-review

Computational pan-genomics: status, promises and challenges

The Computational Pan-Genomics Consortium, Mäkinen, V. A. T. & Valenzuela, S. D. A., Jan 2018, In : Briefings in Bioinformatics. 19, 1, p. 118-135 18 p.

Research output: Contribution to journalArticleScientificpeer-review

Open Access
Open Access
File

Editorial: Special Issue on "Combinatorial Algorithms" (IWOCA 2016)

Makinen, V. & Puglisi, S. J., Aug 2018, In : Theory of Computing Systems. 62, 6, p. 1349-1350 2 p.

Research output: Contribution to journalEditorialScientific

Open Access
File

Error correcting optical mapping data

Mukherjee, K., Washimkar, D., Muggli, M. D., Salmela, L. & Boucher, C., 25 May 2018, In : GigaScience. 7, 6, p. 1-10 10 p.

Research output: Contribution to journalArticleScientificpeer-review

Open Access
File

Evaluating approaches to find exon chains based on long reads

Kuosmanen, A., Norri, T. & Mäkinen, V., May 2018, In : Briefings in Bioinformatics. 19, 3, p. 404-414 11 p.

Research output: Contribution to journalArticleScientificpeer-review

Open Access
File

Hybrid Indexing Revisited

Ferrada, H., Kempa, D. & Puglisi, S. J., 2018, 2018 Proceedings of the Twentieth Workshop on Algorithm Engineering and Experiments (ALENEX). Pagh, R. & Venkatasubramanian, S. (eds.). Society for Industrial and Applied Mathematics, p. 1-8 8 p.

Research output: Chapter in Book/Report/Conference proceedingChapterScientificpeer-review

Kermit: Guided Long Read Assembly using Coloured Overlap Graphs

Walve, R. M., Rastas, P. M. A. & Salmela, L. M., 2018, 18th International Workshop on Algorithms in Bioinformatics (WABI 2018). Parida, L. & Ukkonen, E. (eds.). Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, p. 11:1-11:11 11 p. (Leibniz International Proceedings in Informatics (LIPIcs); vol. 113).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Open Access
File

Minimum Segmentation for Pan-genomic Founder Reconstruction in Linear Time

Norri, T., Cazaux, B., Kosolobov, D. & Mäkinen, V., 2018, 18th International Workshop on Algorithms in Bioinformatics (WABI 2018). Parida, L. & Ukkonen, E. (eds.). Dagstuhl: Schloss Dagstuhl Leibniz Center for Informatics, p. 15:1-15:15 15 p. (Leibniz International Proceedings in Informatics (LIPIcs); vol. 113).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Open Access
File

Relations Between Greedy and Bit-Optimal LZ77 Encodings

Kosolobov, D., 2018, Relations Between Greedy and Bit-Optimal LZ77 Encodings. Niedermeier, R. & Vallée, B. (eds.). Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, p. 46:1-46:14 14 p. 46. (Leibniz International Proceedings in Informatics (LIPIcs); vol. 96).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Open Access
File

Relative Suffix Trees

Farruggia, A., Gagie, T., Navarro, G., Puglisi, S. J. & Sirén, J., May 2018, In : Computer Journal. 61, 5, p. 773-788 16 p.

Research output: Contribution to journalArticleScientificpeer-review

Open Access
File

Towards pan-genome read alignment to improve variation calling

Valenzuela, D., Norri, T., Välimäki, N., Pitkänen, E. & Mäkinen, V., 9 May 2018, In : BMC Genomics. 19, 8 p., 87.

Research output: Contribution to journalArticleScientificpeer-review

Open Access
File

Using Minimum Path Cover to Boost Dynamic Programming on DAGs: Co-linear Chaining Extended

Kuosmanen, A., Paavilainen, T., Gagie, T., Chikhi, R., Tomescu, A. & Mäkinen, V., Apr 2018, Research in Computational Molecular Biology : 22nd Annual International Conference, RECOMB 2018, Paris, France, April 21-24, 2018, Proceedings. Raphael, B. J. (ed.). Cham: Springer International Publishing AG, p. 105-121 17 p. (Lecture Notes in Bioinformatics; vol. 10812).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Open Access
File
2017

Accurate self-correction of errors in long reads using de Bruijn graphs

Salmela, L., Walve, R., Rivals, E. & Ukkonen, E., 15 Mar 2017, In : Bioinformatics. 33, 6, p. 799-806 8 p.

Research output: Contribution to journalArticleScientificpeer-review

Open Access
File

A framework for space-efficient read clustering in metagenomic samples

Alanko, J., Cunial, F., Belazzougui, D. & Mäkinen, V., 14 Mar 2017, In : BMC Bioinformatics. 18, Suppl 3, 12 p., 59.

Research output: Contribution to journalArticleScientificpeer-review

Open Access
File

Algorithms and Data Structures for Sequence Analysis in the Pan-Genomic Era

Valenzuela, S. D. A., 9 Jun 2017, Helsinki: University of Helsinki. 74 p.

Research output: ThesisDoctoral ThesisCollection of Articles

Open Access

Block Graphs in Practice

Gagie, T., Hoobin, C. & Puglisi, S. J., Jun 2017, In : Mathematics in Computer Science. 11, 2, p. 191-196 6 p.

Research output: Contribution to journalArticleScientificpeer-review

Open Access
File

Disentangled long-read de Bruijn graphs via optical maps

Alipahani, B., Salmela, L., Puglisi, S. J., Muggli, M. & Boucher, C., 2017, 17th International Workshop on Algorithms in Bioinformatics, WABI 2017. Schwartz, R. & Reinert, K. (eds.). Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, p. 1:1-1:14 14 p. (Leibniz International Proceedings in Informatics; vol. 88).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Open Access
File

Document retrieval on repetitive string collections

Gagie, T., Hartikainen, A., Karhu, K., Kärkkäinen, J., Navarro, G., Puglisi, S. J. & Sirén, J., Jun 2017, In : Information Retrieval Journal. 20, 3, p. 253-291 39 p.

Research output: Contribution to journalArticleScientificpeer-review

Open Access
File

emMAW: computing minimal absent words in external memory

Héliou, A., Pissis, S. P. & Puglisi, S. J., 1 Sep 2017, In : Bioinformatics. 33, 17, p. 2746-2749 4 p.

Research output: Contribution to journalArticleScientificpeer-review

Open Access
File

Engineering External Memory Induced Suffix Sorting

Kärkkäinen, J., Kempa, D., Puglisi, S. J. & Zhukova, B., 2017, 2017 Proceedings of the Ninteenth Workshop on Algorithm Engineering and Experiments (ALENEX). Fekete, S. & Ramachandran, V. (eds.). Society for Industrial and Applied Mathematics, p. 98-108 11 p.

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Greedy Shortest Common Superstring Approximation in Compact Space

Alanko, J. & Norri, T., 6 Sep 2017, String Processing and Information Retrieval: 24th International Symposium, SPIRE 2017, Palermo, Italy, September 26-29, 2017, Proceedings. Fici, G., Sciortino, M. & Venturini, R. (eds.). Cham: Springer International Publishing AG, p. 1-13 13 p. (Lecture Notes in Computer Science; vol. 10508).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Open Access
File

Interval scheduling maximizing minimum coverage

Mäkinen, V., Staneva, V., Tomescu, A. I., Valenzuela, D. & Wilzbach, S., 10 Jul 2017, In : Discrete Applied Mathematics. 225, p. 130-135 6 p.

Research output: Contribution to journalArticleScientificpeer-review

Open Access
File

LZ-End Parsing in Compressed Space

Kempa, D. & Kosolobov, D., 2017, DCC 2017: 2017 Data Compression Conference. Bilgin, A., Marcellin, MW., SerraSagrista, J. & Storer, JA. (eds.). Los Alamitos, CA: IEEE, p. 350-359 10 p. (IEEE Data Compression Conference).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Open Access
File

LZ-End Parsing in Linear Time

Kempa, D. & Kosolobov, D., 2017, 25th Annual European Symposium on Algorithms (ESA 2017). Pruhs, K. & Sohler, C. (eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 14 p. 53. (Leibniz International Proceedings in Informatics (LIPIcs); vol. 87).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Open Access
File