Source: https://www.cs.helsinki.fi/u/vmakinen/papers/index.html
Timestamp: 2019-04-19 22:18:05+00:00

Document:
The copyrights of the below manuscripts belong to the publishers, so I ask you to use the preprints for your personal use only.
Nidia Obscura Acosta, Veli Mäkinen, Alexandru I. Tomescu. A safe and complete algorithm for metagenomic assembly.
Algorithms for Molecular Biology, 13:3, 2018.
Romeo Rizzi, Massimo Cairo, Veli Mäkinen, Alexandru I. Tomescu, Daniel Valenzuela. Hardness of Covering Alignment: Phase Transition in Post-Sequence Genomics.
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.
Riku Walve, Leena Salmela, Veli Mäkinen. Variant genotyping with gap filling.
Veli Mäkinen, Valeria Staneva, Alexandru I. Tomescu, Daniel Valenzuela, Sebastian Wilzbach. Interval scheduling maximizing minimum coverage.
Anna Kuomanen, Tuukka Norri, Veli äkinen. Evaluating Approaches to Find Exon Chains based on Long Reads.
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.
T. Marschall et al. Computational Pan-Genomics: Status, Promises and Challenges.
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.
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.
Roland Wittler, Tobias Marschall, Alexander Schönhuth, Veli Mäkinen. Repeat- and Error-Aware Comparison of Deletions.
Karen E. van Rens, Veli Mäkinen, and Alexandru I. Tomescu. SNV-PPILP: Refined SNV calling for tumor data using perfect phylogenies and ILP.
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.
Veli Mäkinen and Daniel Valenzuela. Recombination-aware alignment of diploid individuals.
Presented at RECOMB-CG 2014. BMC Genomics, 15(Suppl 6):S15, 2014.
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.
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.
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.
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.
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).
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).
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).
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.
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.
Leena Salmela, Veli Mäkinen, Niko Välimäki, Johannes Ylinen, and Esko Ukkonen. Fast Scaffolding with Small Independent Mixed Integer Programs.
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.
Stanislav Angelov, Shunsuke Inenaga, Teemu Kivioja, and Veli Mäkinen: Missing Pattern Discovery. Journal of Discrete Algorithms, 9(2):153-165, 2011.
Kjell Lemström, Niko Mikkilä, and Veli Mäkinen: Filtering methods for content-based retrieval on indexed symbolic music databases.
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.
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.
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).
Veli Mäkinen: Peak Alignment using Restricted Edit Distances.
Biomolecular Engineering, Vol. 24, Issue 3, pages 337-342, September 2007.
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.
Kimmo Fredriksson, Veli Mäkinen, and Gonzalo Navarro. Rotation and Lighting Invariant Template Matching.
Information and Computation, 205(7):1096--1113, 2007.
Gonzalo Navarro and Veli Mäkinen: Compressed Full-Text Indexes.
ACM Computing Surveys, Vol. 39, No. 1, Article 2, 2007.
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.
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.
Veli Mäkinen and Gonzalo Navarro: Succinct Suffix Arrays based on Run-Length Encoding.
Nordic Journal of Computing, 12(1):40-66, 2005.
Veli Mäkinen, Gonzalo Navarro and Esko Ukkonen: Transposition Invariant String Matching.
Journal of Algorithms, 56(2):124-153, 2005.
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.
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.
Veli Mäkinen, Gonzalo Navarro and Esko Ukkonen: Approximate Matching of Run-length Compressed Strings.
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).
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.
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.
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.
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.
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.
Veli Mäkinen and Daniel Valenzuela. Diploid alignments and haplotyping.
In Proc. ISBRA 2015, Springer, LNCS 9096, pp. 235-246, 2015.
In Proc. RECOMB 2015, LNBI 9029, pp. 281–292, 2015.
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.
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.
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.
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.
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.
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.
In Proc. 11th International Workshop on Algorithms in Bioinformatics (WABI 2011), Springer, LNCS 6833, pp. 270-281, 2011.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
In Proc. 14th Annual Symposium on Combinatorial Pattern Matching (CPM 2003), Springer-Verlag LNCS 2676, pp. 237-253, Morelia, Mexico, June, 2003.
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.
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.
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.
In Proc. 12th Annual Symposium on Combinatorial Pattern Matching (CPM 2001), Springer-Verlag LNCS 2089, pp. 31-49, Jerusalem, July 2001.
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.
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.
Djamal Belazzougui, Veli Mäkinen, Daniel Valenzuela. Compressed Suffix Array. Encyclopedia of Algorithms, 2015.
Veli Mäkinen: Algoritmitutkimuksen rooli bioinformatiikassa. Tietojenkäsittelytiede 32:10-15, 2011.
Veli Mäkinen: Kauniita algoritmeja vääriin ongelmiin Luova, Nuorten luonnontiedeverkkolehti, 14.12.2008.
Veli Mäkinen: Compressed Suffix Array. In M. Kao (editor), Encyclopedia of Algorithms. Springer-Verlag, pages 174-176, 2008.
Veli Mäkinen and Gonzalo Navarro: Compressed Text Indexing. In M. Kao (editor), Encyclopedia of Algorithms. Springer-Verlag, pages 176-178, 2008.
Veli Mäkinen and Esko Ukkonen: Point Pattern Matching. In M. Kao (editor), Encyclopedia of Algorithms. Springer-Verlag, pages 657-660, 2008.
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.
Parameterized approximate string matching and local-similarity-based point-pattern matching. Department of Computer Science, University of Helsinki, Report A-2003-6, August 2003.

References: V. 

V. 
 V. 

V. 
 V. 
 V.