Department of Computer Science

Publications of Veli Mäkinen - check new homepage for latest

The copyrights of the below manuscripts belong to the publishers, so I ask you to use the preprints for your personal use only.

Journal articles

  1. Nidia Obscura Acosta, Veli Mäkinen, Alexandru I. Tomescu. A safe and complete algorithm for metagenomic assembly.
    Algorithms for Molecular Biology, 13:3, 2018.
    [Article online]

  2. Romeo Rizzi, Massimo Cairo, Veli Mäkinen, Alexandru I. Tomescu, Daniel Valenzuela. Hardness of Covering Alignment: Phase Transition in Post-Sequence Genomics.
    Accepted to APBC 2018. To appear in IEEE/ACM TCBB (subject to revisions)

  3. Daniel Valenzuela, Tuukka Norri, Niko Välimäki, Esa Pitkänen, Veli Mäkinen. Towards Pan-Genome Read Alignment to Improve Variation Calling.
    Accepted to APBC 2018. To appear in BMC Genomics.

  4. Riku Walve, Leena Salmela, Veli Mäkinen. Variant genotyping with gap filling.
    PLOS ONE, 2017.
    [Article online]

  5. Veli Mäkinen, Valeria Staneva, Alexandru I. Tomescu, Daniel Valenzuela, Sebastian Wilzbach. Interval scheduling maximizing minimum coverage.
    Discrete Applied Mathematics, 2017. [Article online]

  6. Anna Kuomanen, Tuukka Norri, Veli äkinen. Evaluating Approaches to Find Exon Chains based on Long Reads.
    Briefings in Bioinformatics, 2017.
    [Article online]

  7. Jarno Alanko, Djamal Belazzougui, Fabio Cunial, and Veli äkinen. A framework for space-efficient read clustering in metagenomic samples.
    BMC Bioinformatics, 18(S-3): 49-60, 2017. Presented atAPBC 2017.
    [Article online]

  8. T. Marschall et al. Computational Pan-Genomics: Status, Promises and Challenges.
    Briefings in Bioinformatics, 2016.
    [Article online]

  9. Leena Salmela, Kristoffer Sahlin, Veli Mäkinen, and Alexandru I. Tomescu. Gap Filling as Exact Path Length Problem.
    Journal of Computational Biology, 23(5):347-361, 2016.
    [Article online]
    [Implementation]

  10. Alexandru I. Tomescu, Travis Gagie, Alex Popa, Romeo Rizzi, Anna Kuosmanen, Veli Mäkinen.
    Explaining a Weighted DAG with Few Paths for Solving Genome-Guided Multi-assembly.
    IEEE/ACM Transactions on Computational Biology and Bioinformatics, 12(6):1345-1354, 2015.
    [Article online]

  11. Roland Wittler, Tobias Marschall, Alexander Schönhuth, Veli Mäkinen. Repeat- and Error-Aware Comparison of Deletions.
    Bioinformatics, Sep 15;31(18):2947-54, 2015.
    [Article online]

  12. Karen E. van Rens, Veli Mäkinen, and Alexandru I. Tomescu. SNV-PPILP: Refined SNV calling for tumor data using perfect phylogenies and ILP.
    Bioinformatics, 31(7):1133-1135, 2015.
    [Article online]

  13. Diego Arroyuelo, Francisco Claude, Sebastian Maneth, Veli Mäkinen, Gonzalo Navarro, Kim Nguyễn, Jouni Sirén, and Niko Välimäki. Fast In-Memory XPath Search using Compressed Indexes.
    Software Practice and Experience, 45(3): 399-434, 2015.
    [Article online]

  14. Veli Mäkinen and Daniel Valenzuela. Recombination-aware alignment of diploid individuals.
    Presented at RECOMB-CG 2014. BMC Genomics, 15(Suppl 6):S15, 2014.
    [Article online]

  15. Romeo Rizzi, Alexandru I. Tomescu, and Veli Mäkinen. On the Complexity of Minimum Path Cover with Subpath Constraints for Multi-Assembly.
    Presented at RECOMB-Seq 2014. BMC Bioinformatics, 15(Suppl 9):S5, 2014.
    [Article online]

  16. Ahola V., Lehtonen R., Somervuo P. et al. The Glanville fritillary genome retains an ancient karyotype and reveals selective chromosomal fusions in Lepidoptera.
    Nature Communications, 5:4737, Sept. 2014.
    [Article online]
    [Genome]

  17. Jouni Sirén, Niko Välimäki, and Veli Mäkinen. Indexing Graphs for Path Queries with Applications in Genome Research.
    IEEE/ACM Transactions on Computational Biology and Bioinformatics, 11(2):375-388, 2014.
    [Article online]
    [Implementation]

  18. S. Gog, K. Karhu, J. Kärkkäinen, V. Mäkinen, and N. Välimäki. Multi-pattern matching with bidirectional indexes.
    Journal on Discrete Algorithms, 24:26-39, 2014.
    [Article online]

  19. V. Mäkinen and J. Rahkola. Haploid to Diploid Alignment for Variation Calling Assessment.
    Presented at RECOMB-CG 2013. BMC Bioinformatics, 14(Suppl 15):S13 (15 October 2013).
    [Article online]
    [Implementation]

  20. A. I. Tomescu, A. Kuosmanen, R. Rizzi, and V. Mäkinen. A Novel Min-Cost Flow Method for Estimating Transcript Expression with RNA-Seq.
    Presented at RECOMB-seq 2013. BMC Bioinformatics, 14(Suppl 5):S15 (10 April 2013).
    [Article online]
    [Implementation]

  21. V. Mäkinen, L. Salmela, and J. Ylinen. Normalized N50 Assembly Metric using Gap-Restricted Co-Linear Chaining.
    BMC Bioinformatics, 13:255 (3 October 2012).
    [Article online]
    [Implementation]

  22. M. Kashif, S. Pietilä, K. Artola, R. A. C. Jones, A. K. Tugume, V. Mäkinen, and J. P. T. Valkonen. Detection of Viruses in Sweetpotatoes from Honduras and Guatemala Augmented by Deep-Sequencing of small-RNAs.
    Plant Disease, 96(10):1430-1437, 2012.
    [Article online]

  23. Niko Välimäki, Susana Ladra and Veli Mäkinen. Approximate all-pairs suffix/prefix overlaps. Information & Computation, 213:49-58, 2012. CPM 2010 Special Issue.
    [Article online]
    [Implementation]

  24. Leena Salmela, Veli Mäkinen, Niko Välimäki, Johannes Ylinen, and Esko Ukkonen. Fast Scaffolding with Small Independent Mixed Integer Programs.
    Bioinformatics 27(23): 3259-3265, 2011.
    [Article online]

  25. Petteri Kaski, Veli Mäkinen, and Patric R. J. östergård: The Cycle Switching Graph of the Steiner Triple Systems of Order 19 is Connected.
    Graphs and Combinatorics, 27(4):539-546, 2011.
    [Preprint]

  26. Stanislav Angelov, Shunsuke Inenaga, Teemu Kivioja, and Veli Mäkinen: Missing Pattern Discovery. Journal of Discrete Algorithms, 9(2):153-165, 2011.
    [Article online]

  27. Veli Mäkinen, Gonzalo Navarro, Jouni Sirén, and Niko Välimäki: Storage and Retrieval of Highly Repetitive Sequence Collections.
    Journal of Computational Biology 17(3):281-308, 2010.
    [Article online]

  28. Kjell Lemström, Niko Mikkilä, and Veli Mäkinen: Filtering methods for content-based retrieval on indexed symbolic music databases.
    Information Retrieval, 13(1):1-21, 2010.
    [Article online]

  29. Johannes Fischer, Veli Mäkinen, and Gonzalo Navarro: Faster Entropy-Bounded Compressed Suffix Trees.
    Theoretical Computer Science, 410(51):5354-5364, 2009.
    [Article online]

  30. Niko Välimäki, Veli Mäkinen, Wolfgang Gerlach, and Kashyap Dixit: Engineering a Compressed Suffix Tree Implementation.
    ACM Journal of Experimental Algorithmics, 14:4.2-4.23, 2009
    [Preprint] [Implementation]

  31. Francois Nicolas, Veli Mäkinen and Esko Ukkonen: Efficient Construction of Maximal and Minimal Representations of Motifs of a String.
    Theoretical Computer Science, 410 (2009) 2999-3005.
    [Preprint]

  32. Veli Mäkinen and Gonzalo Navarro: Dynamic Entropy-Compressed Sequences and Full-Text Indexes.
    ACM Transactions on Algorithms, 4(3):article 32, 2008.
    [Preprint] [Erratum]

  33. Sebastian Böcker and Veli Mäkinen: Combinatorial Approaches for Mass Spectra Recalibration.
    IEEE/ACM Transactions on Computational Biology and Bioinformatics, 5(1):91-100, 2008.
    [Preprint]

  34. Veli Mäkinen and Gonzalo Navarro: Rank and Select Revisited and Extended.
    Theoretical Computer Science, 387(3):332-347, 2007. Special issue on the Burrows-Wheeler Transform (see the forewords by the editors and by Mike Burrows).
    [Abstract] [Bibtex] [Preprint] [Article online]

  35. Veli Mäkinen: Peak Alignment using Restricted Edit Distances.
    Biomolecular Engineering, Vol. 24, Issue 3, pages 337-342, September 2007.
    [Abstract] [Bibtex] [Article online]

  36. Paolo Ferragina, Giovanni Manzini, Veli Mäkinen, and Gonzalo Navarro: Compressed Representations of Sequences and Full-Text Indexes.
    ACM Transactions on Algorithms, Vol. 3, Issue 2, Article 20, May 2007.
    [Preprint] [Article online]

  37. Kimmo Fredriksson, Veli Mäkinen, and Gonzalo Navarro. Rotation and Lighting Invariant Template Matching.
    Information and Computation, 205(7):1096--1113, 2007.
    [Preprint] [Article online]

  38. Gonzalo Navarro and Veli Mäkinen: Compressed Full-Text Indexes.
    ACM Computing Surveys, Vol. 39, No. 1, Article 2, 2007.
    [Preprint] [Article online]

  39. Niko Välimäki, Wolfgang Gerlach, Kashyap Dixit, and Veli Mäkinen. Compressed Suffix Tree - A Basis for Genome-scale Sequence Analysis,
    Bioinformatics, 23:629-630, 2007.
    [Bibtex] [Preprint] [Article online]

  40. Kimmo Fredriksson, Veli Mäkinen, and Gonzalo Navarro: Flexible Music Retrieval in Sublinear Time.
    International Journal of Foundations of Computer Science (IJFCS), 17(6):1345-1364, 2006.
    [Abstract] [Bibtex] [Preprint]

  41. Szymon Grabowski, Gonzalo Navarro, Rafal Przywarski, Alejandro Salinger, and Veli Mäkinen: A Simple Alphabet-Independent FM-Index.
    International Journal of Foundations of Computer Science (IJFCS), 17(6):1365-1384, 2006.
    [Abstract] [Bibtex] [Preprint]

  42. Veli Mäkinen and Gonzalo Navarro: Succinct Suffix Arrays based on Run-Length Encoding.
    Nordic Journal of Computing, 12(1):40-66, 2005.
    [Abstract] [Bibtex] [Preprint]

  43. Veli Mäkinen, Gonzalo Navarro and Esko Ukkonen: Transposition Invariant String Matching.
    Journal of Algorithms, 56(2):124-153, 2005.
    [Abstract] [ScienceDirect] [Bibtex] [Preprint]

  44. Kjell Lemström and Veli Mäkinen: On Finding Minimum Splitting of Pattern in Multi-Track String Matching.
    Journal of Discrete Algorithms, 3(2-4):248-266, 2005.
    [Abstract] [ScienceDirect] [Bibtex] [Preprint]

  45. Veli Mäkinen: Compact Suffix Array - A Space-Efficient Full-Text Index.
    Fundamenta Infomaticae, Special Issue - Computing Patterns in Strings, 56(1-2):191-210, 2003.
    [Abstract] [Bibtex] [Preprint]

  46. Veli Mäkinen, Gonzalo Navarro and Esko Ukkonen: Approximate Matching of Run-length Compressed Strings.
    Algorithmica, 35(4):347-369, 2003.
    [Abstract] [Bibtex] [Preprint]

Conference papers

  1. Anna Kuosmanen, Topi Paavilainen, Travis Gagie, Rayan Chikhi, Alexandru I. Tomescu, and Veli Mäkinen. Using Minimum Path Cover to Boost Dynamic Programming on DAGs: Co-Linear Chaining Extended. Accepted to RECOMB 2018 (subject to revisions).

  2. Djamal Belazzougui, Travis Gagie, Veli Mäkinen and Marco Previtali. Fully Dynamic de Bruijn Graphs.
    In Proc. SPIRE 2016, Springer, LNCS 9954, pp. 145-152, 2016.

  3. Mikko Rautiainen, Leena Salmela, and Veli Mäkinen. Identification of variant compositions in related strains without reference.
    In Proc. Conference on Algorithms for Computational Biology (ALCOB 2016), Springer, LNCS 9702, pp. 158-170, 2016.

  4. Ahmed Sobih, Veli Mäkinen, Alexandru I. Tomescu. MetaFlow: Metagenomic profiling based on whole-genome coverage analysis with min-cost flows.
    In Proc. RECOMB 2016, Springer, LNCS 9649, pp. 111-121, 2016.

  5. Anna Kuosmanen, Ahmed Sobih, Romeo Rizzi, Veli Mäkinen, and Alexandru I. Tomescu. On Using Longer RNA-seq Reads to Improve Transcript Prediction Accuracy.
    In Proc. BIOINFORMATICS 2016, SciTePress, pp. 272-277, 2016.
    [Preprint]

  6. Djamal Belazzougui, Travis Gagie, Veli Mäkinen, Marco Previtali, and Simon Puglisi. Bidirectional BWT-Based De Bruijn Graphs.
    In Proc. LATIN 2016, Springer, LNCS 9644, pp. 164-178, 2016.

  7. Veli Mäkinen and Daniel Valenzuela. Diploid alignments and haplotyping.
    In Proc. ISBRA 2015, Springer, LNCS 9096, pp. 235-246, 2015.

  8. Leena Salmela, Kristoffer Sahlin, Veli Mäkinen, and Alexandru I. Tomescu. Gap Filling as Exact Path Length Problem.
    In Proc. RECOMB 2015, LNBI 9029, pp. 281–292, 2015.
    [Article online]
    [Implementation]

  9. A. I. Tomescu, A. Kuosmanen, R. Rizzi, and V. Mäkinen. A Novel Combinatorial Method for Estimating Transcript Expression with RNA-Seq: Bounding the Number of Paths.
    In Proc. WABI 2013, Springer, LNCS 8126, pp. 85-98, 2013.
    [Article online]
    [Implementation]

  10. Djamal Belazzougui, Fabio Cunial, Juha Kärkkäinen, and Veli Mäkinen. Versatile succinct representations of the bidirectional Burrows-Wheeler transform.
    In Proc. ESA 2013.Springer, LNCS 8125, pp. 133-144, 2013.
    [Article online]
    [Implementation of MUMs]

  11. Simon Gog, Kalle Karhu, Juha Kärkkäinen, Veli Mäkinen, and Niko Välimäki. Multi-Pattern Matching with Bidirectional Indexes.
    In Proc. 18th Annual International Conference on Computing and Combinatorics (COCOON 2012), Springer, LNCS 7434, pp. 384-395, 2012.
    [Article online]

  12. Johannes Fischer, Travis Gagie, Tsvi Kopelowitz, Moshe Lewenstein, Veli Mäkinen, Leena Salmela, and Niko Välimäki. Forbidden Patterns.
    In Proc. 10th Latin American Symposium on Theoretical Informatics (LATIN 2012), Springer, LNCS 7256, pp. 327-337, 2012.
    [Article online]

  13. Travis Gagie, Kalle Karhu, Juha Kärkkäinen, Veli Mäkinen, Leena Salmela, and Jorma Tarhio: Indexed Multi-Pattern Matching.
    In Proc. 10th Latin American Symposium on Theoretical Informatics (LATIN 2012), Springer, LNCS 7256, pp. 399-407, 2012.
    [Article online]

  14. Markus Heinonen, Niko Välimäki, Veli Mäkinen, and Juho Rousu: Efficient Path Kernels for Reaction Function Prediction.
    In Proc. International Conference on Bioinformatics Models, Methods and Algorithms (BIOINFORMATICS 2012), SciTePress, pp. 202-207, 2012.
    [Article]

  15. Jouni Sirén, Niko Välimäki, and Veli Mäkinen: Indexing Finite Language Representation of Population Genotypes.
    In Proc. 11th International Workshop on Algorithms in Bioinformatics (WABI 2011), Springer, LNCS 6833, pp. 270-281, 2011.
    [Article online]
    [Full version]
    [Implementation]

  16. Niko Välimäki, Susana Ladra, and Veli Mäkinen: Approximate All-Pairs Suffix/Prefix Overlaps.
    In Proc. 21st Annual Symposium on Combinatorial Pattern Matching (CPM 2010), Springer-Verlag, LNCS 6129, pp. 76-87, New York, USA, 21-23 June 2010.
    [Article online]
    [Implementation]

  17. Diego Arroyuelo, Francisco Claude, Sebastian Maneth, Veli Mäkinen, Gonzalo Navarro, Kim Nguyen, Jouni Sirén, and Niko Välimäki: Fast In-Memory XPath Search using Compressed Indexes.
    In Proc. 26th IEEE International Conference on Data Engineering (ICDE 2010), IEEE, pp. 417-428, 2010.
    [Preprint]

  18. Veli Mäkinen, Gonzalo Navarro, Jouni Sirén, and Niko Välimäki. Storage and Retrieval of Individual Genomes.
    In Proc. 13th Annual International Conference on Research in Computational Molecular Biology (RECOMB 2009), Springer-Verlag LNCS 5541, pp. 121-137, Tucson, Arizona, May 18-21, 2009.
    [Article online]
    [Preprint]
    [Implementation]

  19. Johannes Fischer, Veli Mäkinen, and Niko Välimäki: Space-Efficient String Mining under Frequency Constraints.
    In Proc. Eighth IEEE International Conference on Data Mining (ICDM 2008), IEEE Computer Society, pages 193-202, Pisa, Italy, December 15-19, 2008.
    [Article online]
    [Preprint]
    [Code]

  20. Jouni Siren, Niko Välimäki, Veli Mäkinen, and Gonzalo Navarro: Run-Length Compressed Indexes Are Superior for Highly Repetitive Sequence Collections.
    In Proc. 15th Symposium on String Processing and Information Retrieval (SPIRE 2008), Springer-Verlag LNCS 5280, pp. 164-175, Melbourne, Australia, November 10-12, 2008.
    [Article online]
    [Preprint]

  21. Kjell Lemström, Niko Mikkilä and Veli Mäkinen: Fast Index Based Filters for Music Retrieval.
    In Proc. International Conference on Music Information Retrieval (ISMIR 2008), pp. 677-682, Philadelphia, USA, September 14-18, 2008.
    [Article online]
    [Preprint]

  22. Johannes Fischer, Veli Mäkinen and Gonzalo Navarro: An(other) Entropy-Bounded Compressed Suffix Tree.
    In Proc. Annual Symposium on Combinatorial Pattern Matching (CPM 2008), Springer-Verlag LNCS 5029, pages 152-165, Pisa, Italy, June 18-20, 2008.
    [Article online]
    [Preprint]

  23. Veli Mäkinen and Gonzalo Navarro: On Self-indexing Images - Image Compression with Added Value.
    In Proc. Data Compression Conference (DCC 2008), IEEE Computer Society, pages 422-431, Snowbird, Utah, USA, March 25-27, 2008.
    [Article online]
    [Preprint]

  24. Veli Mäkinen and Gonzalo Navarro: Implicit Compression Boosting with Applications to Self-Indexing.
    In Proc. 14th Symposium on String Processing and Information Retrieval (SPIRE 2007), Springer-Verlag LNCS 4726, pages 214-226, Santiago, Chile, October 29-31, 2007.
    [Article online]
    [Preprint]

  25. Niko Välimäki and Veli Mäkinen: Space-efficient Algorithms for Document Retrieval.
    In Proc. 18th Annual Symposium on Combinatorial Pattern Matching (CPM 2007), Springer-Verlag LNCS 4580, pp. 205-215, London, Ontario, Canada, July 9-11, 2007.
    [Bibtex] [Preprint]

  26. Niko Välimäki, Wolfgang Gerlach, Kashyap Dixit, and Veli Mäkinen: Engineering a Compressed Suffix Tree Implementation.
    In Proc. 6th Workshop on Experimental Algorithms (WEA 2007), Springer-Verlag LNCS 4525, pp. 217-228, Rome, Italy, June 6-8, 2007.
    [Bibtex]
    [Preprint]
    [Code]

  27. Veli Mäkinen and Gonzalo Navarro. Dynamic Entropy-Compressed Sequences and Full-Text Indexes.
    In Proc. 17th Annual Symposium on Combinatorial Pattern Matching (CPM 2006), Springer-Verlag LNCS 4009, pp. 306-317, Barcelona, Spain, July 5-7, 2006.
    [Abstract] [Bibtex] [Preprint] (see the journal version)

  28. Veli Mäkinen and Gonzalo Navarro. Position-Restricted Substring Searching.
    In Proc. 7th Latin American Symposium on Theoretical Informatics (LATIN 2006), Springer-Verlag LNCS 3887, pp. 703-714, Valdivia, Chile, March 20-24, 2006.
    [Abstract] [Bibtex] [Preprint] (see the journal version)

  29. Kimmo Fredriksson, Veli Mäkinen, and Gonzalo Navarro. Flexible Music Retrieval in Sublinear Time.
    In Proceedings of the 10th Prague Stringology Conference (PSC'05), pp. 174-188, Prague, Czech Republic, 29-31 August, 2005.
    [Abstract] [Bibtex] [Preprint] (see the journal version)

  30. Szymon Grabowski, Veli Mäkinen, Gonzalo Navarro, and Alejandro Salinger. A Simple Alphabet-Independent FM-Index.
    In Proceedings of the 10th Prague Stringology Conference (PSC'05), pp. 230-244, Prague, Czech Republic, 29-31 August, 2005.
    [Abstract] [Bibtex] [Preprint] (see the journal version)

  31. Veli Mäkinen. Peak Alignment using Restricted Edit Distances.
    In Proc. 6th International Symposium on Computational Biology and Genome Informatics (CBGI 2005), Salt Lake City, Utah, USA, July 21-26, 2005.
    [Preprint] (see the journal version)

  32. Veli Mäkinen and Gonzalo Navarro. Succinct Suffix Arrays based on Run-Length Encoding.
    In Proc. 16th Annual Symposium on Combinatorial Pattern Matching (CPM 2005), LNCS 3537, pp. 45-56, Jeju Island, Korea, June 19-22, 2005.
    [Abstract] [Bibtex] [Preprint] (See the journal version)

  33. Rodrigo González, Szymon Grabowski, Veli Mäkinen, and Gonzalo Navarro. Practical Implementation of Rank and Select Queries.
    In Poster Proceedings of 4th International Workshop on Efficient and Experimental Algorithms (WEA'05), CTI Press and Ellinika Grammata, Santorini Island, Greece, May 10-13, 2005.
    [Abstract] [Bibtex] [PostScript]

  34. Sebastian Böcker and Veli Mäkinen: Maximum Line-Pair Stabbing Problem and its Variations.
    In Proc. 21st European Workshop on Computational Geometry (EWCG'05), pp. 183-186, Eindhoven, Netherlands, March 9-11, 2005.
    [Article online] (see the journal version)

  35. Veli Mäkinen, Gonzalo Navarro, and Kunihiko Sadakane: Advantages of Backward Searching - Efficient Secondary Memory and Distributed Implementation of Compressed Suffix Arrays.
    In Proc. 15th Annual Symposium on Algorithms and Computation (ISAAC 2004), Springer-Verlag LNCS 3341, pp. 681-692, Hong Kong, December 20-22, 2004.
    [Abstract] [Bibtex] [Preprint]

  36. Paolo Ferragina, Giovanni Manzini, Veli Mäkinen, and Gonzalo Navarro: An Alphabet-Friendly FM-index.
    In Proc. 11th Symposium on String Processing and Information Retrieval (SPIRE 2004), Springer-Verlag LNCS 3246, pp. 150-160, Padova, Italy, October 5-8, 2004.
    [Abstract] [Bibtex] [Preprint] (See the journal version)

  37. Szymon Grabowski, Veli Mäkinen, and Gonzalo Navarro: First Huffman, then Burrows-Wheeler: A Simple Alphabet-Independent FM-Index (Abstract).
    In Proc. 11th Symposium on String Processing and Information Retrieval (SPIRE 2004), Springer-Verlag LNCS 3246, pp. 210-211, Padova, Italy, October 5-8, 2004.
    [Abstract] [Bibtex] [Preprint] (See the journal version)

  38. Shunsuke Inenaga, Teemu Kivioja, and Veli Mäkinen: Finding Missing Patterns.
    In Proc. 4th Workshop on Algorithms in Bioinformatics (WABI 2004), Springer-Verlag LNBI 3240, pp. 463-474, Bergen, Norway, September 14-17, 2004.
    [Abstract] [Bibtex] [Preprint]

  39. Veli Mäkinen and Gonzalo Navarro: Compressed Compact Suffix Arrays.
    In Proc. 15th Annual Symposium on Combinatorial Pattern Matching (CPM 2004), Springer-Verlag LNCS 3109, pp. 420-433, Istanbul, Turkey, July 5-7, 2004.
    [Abstract] [Bibtex] [Preprint]

  40. Kimmo Fredriksson, Veli Mäkinen, and Gonzalo Navarro: Rotation and Lighting Invariant Template Matching.
    In Proc. Latin American Theoretical Informatics (LATIN 2004), Springer-Verlag LNCS 2976, pp. 39-48, Buenos Aires, Argentina, April 5-9, 2004.
    [Abstract] [Bibtex] [pdf] (See the journal version)

  41. Esko Ukkonen, Kjell Lemström and Veli Mäkinen: Geometric Algorithms for Transposition Invariant Content-Based Music Retrieval.
    In Proc. 4th International Conference on Music Information Retrieval (ISMIR 2003), pp. 193-199, Baltimore, Maryland, USA, October, 2003.
    [Abstract] [Bibtex] [Preprint]

  42. Veli Mäkinen, Gonzalo Navarro and Esko Ukkonen: Matching Numeric Strings under Noise.
    In Proc. Prague Stringology Conference (PSC'03), pp. 99-110, Czech Technical University, Prague, September, 2003.
    [Abstract] [Bibtex] [Preprint] (See the journal version)

  43. Kjell Lemström and Veli Mäkinen: On Finding Minimum Splitting of Pattern in Multi-Track String Matching.
    In Proc. 14th Annual Symposium on Combinatorial Pattern Matching (CPM 2003), Springer-Verlag LNCS 2676, pp. 237-253, Morelia, Mexico, June, 2003.
    [Abstract] [Bibtex] [Preprint] (See the journal version)

  44. Veli Mäkinen, Gonzalo Navarro and Esko Ukkonen: Algorithms for Transposition Invariant String Matching.
    In Proc. 20th International Symposium on Theoretical Aspects of Computer Science (STACS 2003), Springer-Verlag LNCS 2607, pp. 191-202, Berlin, February, 2003.
    [Abstract] [Bibtex] [Preprint] (See the journal version)

  45. Veli Mäkinen and Esko Ukkonen: Local Similarity Based Point-Pattern Matching.
    In Proc. 13th Annual Symposium on Combinatorial Pattern Matching (CPM 2002), Springer-Verlag LNCS 2373, pp. 115-132, Fukuoka, Japan, July, 2002.
    [Abstract] [Bibtex] [Preprint] (Extended results appear in the phd thesis)

  46. Veli Mäkinen: Using Edit Distance in Point-Pattern Matching.
    In Proc. 8th Symposium on String Processing and Information Retrieval (SPIRE 2001), IEEE CS Press, pp. 153-161, Laguna De San Rafael, Chile, November, 2001.
    [Abstract] [Bibtex] [Preprint] (Extended results appear in the phd thesis)

  47. Veli Mäkinen, Gonzalo Navarro and Esko Ukkonen: Approximate Matching of Run-length Compressed Strings.
    In Proc. 12th Annual Symposium on Combinatorial Pattern Matching (CPM 2001), Springer-Verlag LNCS 2089, pp. 31-49, Jerusalem, July 2001.
    [Abstract] [Bibtex] [Preprint] (See the journal version)

  48. Veli Mäkinen: Trade off Between Compression and Search Times in Compact Suffix Array.
    In Proc. 3rd Workshop on Algorithm Engineering and Experimentation (ALENEX 2001), Springer-Verlag LNCS 2153, pp. 189-201, Washington D.C., January 2001.
    [Abstract] [Bibtex] [Preprint] (this and the below are now joined into a journal paper)

  49. Veli Mäkinen: Compact Suffix Array.
    In Proc. 11th Annual Symposium on Combinatorial Pattern Matching (CPM 2000). Springer-Verlag LNCS 1848, pp. 305-319, Montréal, June 2000.
    [Abstract] [Bibtex] [Preprint]

Books, book chapters, edited proceedings, and review articles

  1. Veli Mäkinen, Simon Puglisi, and Leena Salmela (editors). Proc. 27th International Workshop on Combinatorial Algorithms (IWOCA 2016), Springer, LNCS 9843, 2016. [SpringerLink]

  2. Veli Mäkinen, Djamal Belazzougui, Fabio Cunial, and Alexandru I. Tomescu. Genome-Scale Algorithm Design: Biological Sequence Analysis in the Era of High-Throughput Sequencing. Cambridge University Press. [Book webpage]

  3. Djamal Belazzougui, Veli Mäkinen, Daniel Valenzuela. Compressed Suffix Array. Encyclopedia of Algorithms, 2015.

  4. Veli Mäkinen: Editorial: Special Issue on Algorithms for Sequence Analysis and Storage. Algorithms, 7(1):186-187, 2014. [Article online]

  5. Veli Mäkinen: Algoritmitutkimuksen rooli bioinformatiikassa. Tietojenkäsittelytiede 32:10-15, 2011.

  6. Veli Mäkinen, Niko Välimäki, Antti Laaksonen, and Riku Katainen: Unified View of Backward Backtracking in Short Read Mapping. In Ukkonen Festschrift 2010 (Eds. Tapio Elomaa, Pekka Orponen, Heikki Mannila), Springer-Verlag, LNCS 6060, pp. 182-195, 2010. [Article online] [Implementation]

  7. Veli Mäkinen: Kauniita algoritmeja vääriin ongelmiin Luova, Nuorten luonnontiedeverkkolehti, 14.12.2008.

  8. Veli Mäkinen: Compressed Suffix Array. In M. Kao (editor), Encyclopedia of Algorithms. Springer-Verlag, pages 174-176, 2008.

  9. Veli Mäkinen and Gonzalo Navarro: Compressed Text Indexing. In M. Kao (editor), Encyclopedia of Algorithms. Springer-Verlag, pages 176-178, 2008.

  10. Veli Mäkinen and Esko Ukkonen: Point Pattern Matching. In M. Kao (editor), Encyclopedia of Algorithms. Springer-Verlag, pages 657-660, 2008.

  11. Veli Mäkinen, Greger Lindén, Inka Kujala (eds.): From Data to Knowledge, National Centre of Excellence, Academy of Finland - Final Report 2002-2007. Report B-2008-1, Department of Computer Science, University of Helsinki, June 2008. 144 pp.

  12. Veli Mäkinen, Greger Lindén, Hannu Toivonen (eds.): Abstract Proceedings of the Summer School on Algorithmic Data Analysis (SADA 2007) and the Annual Hecse Poster Session. Report B-2007-4, Department of Computer Science, University of Helsinki, May 2007. 108 + viii pp. [Pdf]

  13. Veli Mäkinen: Itseindeksit - Kun tiivistetty teksti ja sen indeksi ovatkin sama asia. Tietojenkäsittelytiede, 25:28-37, 2006. [Preprint]

  14. Esko Ukkonen, Kjell Lemström and Veli Mäkinen: Sweepline the music! In Computer Science in Perspective, Essays Dedicated to Thomas Ottmann, Eds. Rolf Klein, Hans-Werner Six, Lutz Wegner, Springer-Verlag LNCS 2598, pp. 330-342, February, 2003. [Abstract] [Bibtex] [Preprint]

Manuscripts etc. whose content is not published elsewhere (not refereed)

  1. A. Bonifati, G. Leighton, V. Mäkinen, S. Maneth, G. Navarro, and A. Pugliese. An In-Memory XQuery/XPath Engine over a Compressed Structured Text Representation, In Proc. Dagstuhl Seminar on Structure-Based Compression of Complex Massive Data, Schloss Dagstuhl, Germany, June 2008. [Article]

  2. Veli Mäkinen: Sub-quadratic Algorithm for Weighted k-Mismatches Problem, Technical report, C-2004-1, Department of Computer Science, University of Helsinki, February 2004. [Bibtex] [PostScript]

PhD thesis

Master's thesis

  • In Finnish: Likimääräisen hahmonetsinnän tehostaminen indeksirakenteiden avulla (Speeding up approximate string matching using index structures), Department of Computer Science, University of Helsinki, Report C-1999-65, October 1999. [Abstract in English] [Thesis in Finnish]

Home