Genome-scale Algorithmics research group / Veli Mäkinen

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

    HELSINGIN YLIOPISTO

    Finland

Publications 2009 2019

2019

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

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

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 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

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

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

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

Run compressed rank/select for large alphabets

Fuentes-Sepulveda, J., Karkkainen, J., Kosolobov, D. & Puglisi, S., 2018, 2018 Data Compression Conference 27–30 March 2018 Snowbird, Utah, USA. Bilgin, A., Marcellin, M. W., Serra-Sagrista, J. & Storer, J. A. (eds.). IEEE, p. 315-324 10 p. (DCC).

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

Safely Filling Gaps with Partial Solutions Common to All Solutions

Salmela, L. & Tomescu, A. I., 15 Jan 2018, 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

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

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

Compressed Spaced Suffix Arrays

Gagie, T., Manzini, G. & Valenzuela, D., Jun 2017, In : Mathematics in Computer Science. 11, 2, p. 151-157 7 p.

Research output: Contribution to journalArticleScientificpeer-review

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

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

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

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

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

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

On Sets and Graphs: Perspectives on Logic and Combinatorics

Omodeo, E. G., Policriti, A. & Tomescu, A. I., May 2017, Springer International Publishing . 275 p.

Research output: Book/ReportBookScientificpeer-review

On Suffix Tree Breadth

Badkobeh, G., Kärkkäinen, J., Puglisi, S. J. & Zhukova, B., 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, p. 68-73 6 p. (Lecture Notes in Computer Science; vol. 10508).

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

On the Size of Lempel-Ziv and Lyndon Factorizations

Kärkkäinen, J., Kempa, D., Nakashima, Y., Puglisi, S. J. & Shur, A. M., 2017, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Vollmer, H. & Vallée, B. (eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 13 p. 45. (Leibniz International Proceedings in Informatics (LIPIcs); vol. 66).

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

Open Access
File

On Two LZ78-style Grammars: Compression Bounds and Compressed-Space Computation

Kosolobov, D., Puglisi, S. J., Kociumaka, T., Gagie, T., Badkobeh, G. & Inenaga, S., 2017, String Processing and Information Retrieval: 24th International Symposium, SPIRE 2017 Palermo, Italy, September 26–29, 2017 Proceedings 123. Fici, G., Sciortino, M. & Venturini, R. (eds.). Cham: Springer, p. 51-67 17 p. (Lecture Notes in Computer Science (LNCS); no. 10508).

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

Open Access

Optimal Omnitig Listing for Safe and Complete Contig Assembly

Cairo, M., Medvedev, P., Acosta, N. O., Rizzi, R. & Tomescu, A. I., 2017, 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017). Radoszewski, J., Kärkkäinen, J. & Rytter, W. (eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, p. 29:1-29:12 29. (Leibniz International Proceedings in Informatics (LIPIcs); vol. 78).

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

Open Access

Palindromic length in linear time

Kosolobov, D., Shur, A. M., Rubinchik, M. & Borozdin, K., 2017, Palindromic length in linear time. Kärkkäinen, J., Radoszewski, J. & Rytter, W. (eds.). Wadern: Leibniz-Zentrum für Informatik, p. 23:1-23:12 12 p. 23. (Leibniz International Proceedings in Informatics (LIPIcs); no. 78).

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

Open Access
File

Safe and Complete Contig Assembly Through Omnitigs

Tomescu, A. I. & Medvedev, P., 1 Jun 2017, In : Journal of Computational Biology. 24, 6, p. 590-602 13 p.

Research output: Contribution to journalArticleScientificpeer-review

Open Access

Set-syllogistics meet combinatorics

Omodeo, E., Policriti, A. & Tomescu, A. I., Feb 2017, In : MSCS : mathematical structures in computer science.. 27, 2 (Special Issue: XIV ICTCS), p. 296-310 15 p.

Research output: Contribution to journalArticleScientificpeer-review

File

String Inference from Longest-Common-Prefix Array

Kärkkäinen, J., Piątkowski, M. & Puglisi, S. J., 2017, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Chatzigiannakis, I., Indyk, P., Kuhn, F. & Muscholl, A. (eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 14 p. 62. (Leibniz International Proceedings in Informatics (LIPIcs); vol. 80).

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

Open Access
File

Succinct colored de Bruijn graphs

Muggli, M. D., Bowe, A., Noyes, N. R., Morley, P. S., Belk, K. E., Raymond, R., Gagie, T., Puglisi, S. J. & Boucher, C., 15 Oct 2017, In : Bioinformatics. 33, 20, p. 3181-3187 7 p.

Research output: Contribution to journalArticleScientificpeer-review

Open Access

Third-generation RNA-sequencing analysis: graph alignment and transcript assembly with long reads

Kuosmanen, A., 20 Dec 2017, Helsinki: University of Helsinki. 133 p.

Research output: ThesisDoctoral ThesisCollection of Articles

Open Access

Tight lower bounds for the longest common extension problem

Kosolobov, D., Sep 2017, In : Information Processing Letters. 125, p. 26-29 4 p.

Research output: Contribution to journalArticleScientificpeer-review