Veli Mäkinen

Affiliations:
  • University of Helsinki


According to our database1, Veli Mäkinen authored at least 127 papers between 2000 and 2024.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
Elastic founder graphs improved and enhanced.
Theor. Comput. Sci., January, 2024

2023
Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails.
Theor. Comput. Sci., October, 2023

Chaining for accurate alignment of erroneous long reads to acyclic variation graphs.
Bioinform., August, 2023

On the Complexity of String Matching for Graphs.
ACM Trans. Algorithms, July, 2023

Algorithms and Complexity on Indexing Founder Graphs.
Algorithmica, June, 2023

Finding Maximal Exact Matches in Graphs.
Proceedings of the 23rd International Workshop on Algorithms in Bioinformatics, 2023

Chaining of Maximal Exact Matches in Graphs.
Proceedings of the String Processing and Information Retrieval, 2023

From Bit-Parallelism to Quantum String Matching for Labelled Graphs.
Proceedings of the 34th Annual Symposium on Combinatorial Pattern Matching, 2023

Genome-Scale Algorithm Design: Bioinformatics in the Era of High-Throughput Sequencing (2nd edition).
Cambridge University Press, ISBN: 9781009341233, 2023

2022
Linear Time Construction of Indexable Elastic Founder Graphs.
Proceedings of the Combinatorial Algorithms - 33rd International Workshop, 2022

Indexable Elastic Founder Graphs of Minimum Height.
Proceedings of the 33rd Annual Symposium on Combinatorial Pattern Matching, 2022

2021
Accurate spliced alignment of long RNA sequencing reads.
Bioinform., 2021

Founder reconstruction enables scalable and seamless pangenomic analysis.
Bioinform., 2021

Algorithms and Complexity on Indexing Elastic Founder Graphs.
Proceedings of the 32nd International Symposium on Algorithms and Computation, 2021

2020
Linear-time String Indexing and Analysis in Small Space.
ACM Trans. Algorithms, 2020

Tailoring r-index for metagenomics.
CoRR, 2020

Conditional Indexing Lower Bounds Through Self-Reducibility.
CoRR, 2020

Linear Time Construction of Indexable Founder Block Graphs.
Proceedings of the 20th International Workshop on Algorithms in Bioinformatics, 2020

Tailoring r-index for Document Listing Towards Metagenomics Applications.
Proceedings of the String Processing and Information Retrieval, 2020

Chaining with Overlaps Revisited.
Proceedings of the 31st Annual Symposium on Combinatorial Pattern Matching, 2020

Scalable Reference Genome Assembly from Compressed Pan-Genome Index with Spark.
Proceedings of the Big Data - BigData 2020, 2020

2019
Hardness of Covering Alignment: Phase Transition in Post-Sequence Genomics.
IEEE ACM Trans. Comput. Biol. Bioinform., 2019

Sparse Dynamic Programming on DAGs with Small Width.
ACM Trans. Algorithms, 2019

Applying the Positional Burrows-Wheeler Transform to all-pairs Hamming distance.
Inf. Process. Lett., 2019

On the Complexity of Exact Pattern Matching in Graphs: Determinism and Zig-Zag Matching.
CoRR, 2019

On the Complexity of Exact Pattern Matching in Graphs: Binary Strings and Bounded Degree.
CoRR, 2019

Bit-parallel sequence-to-graph alignment.
Bioinform., 2019

MIPUP: minimum perfect unmixed phylogenies for multi-sampled tumors via branchings and ILP.
Bioinform., 2019

Linear time minimum segmentation enables scalable founder reconstruction.
Algorithms Mol. Biol., 2019

Linear Time Maximum Segmentation Problems in Column Stream Model.
Proceedings of the String Processing and Information Retrieval, 2019

2018
Editorial: Special Issue on "Combinatorial Algorithms" (IWOCA 2016).
Theory Comput. Syst., 2018

Bidirectional Variable-Order de Bruijn Graphs.
Int. J. Found. Comput. Sci., 2018

Assembling Omnitigs using Hidden-Order de Bruijn Graphs.
CoRR, 2018

Minimum Segmentation for Pan-genomic Founder Reconstruction in Optimal Time.
CoRR, 2018

Towards pan-genome read alignment to improve variation calling.
BMC Genom., 2018

Evaluating approaches to find exon chains based on long reads.
Briefings Bioinform., 2018

A safe and complete algorithm for metagenomic assembly.
Algorithms Mol. Biol., 2018

Minimum Segmentation for Pan-genomic Founder Reconstruction in Linear Time.
Proceedings of the 18th International Workshop on Algorithms in Bioinformatics, 2018

Using Minimum Path Cover to Boost Dynamic Programming on DAGs: Co-linear Chaining Extended.
Proceedings of the Research in Computational Molecular Biology, 2018

2017
Interval scheduling maximizing minimum coverage.
Discret. Appl. Math., 2017

Speeding up Dynamic Programming on DAGs through a Fast Approximation of Path Cover.
CoRR, 2017

A framework for space-efficient read clustering in metagenomic samples.
BMC Bioinform., 2017

2016
Point Pattern Matching.
Encyclopedia of Algorithms, 2016

Compressed Text Indexing.
Encyclopedia of Algorithms, 2016

Compressed Suffix Array.
Encyclopedia of Algorithms, 2016

Gap Filling as Exact Path Length Problem.
J. Comput. Biol., 2016

Diploid Alignment is NP-hard.
CoRR, 2016

Fully Dynamic de Bruijn Graphs.
Proceedings of the String Processing and Information Retrieval, 2016

MetaFlow: Metagenomic Profiling Based on Whole-Genome Coverage Analysis with Min-Cost Flows.
Proceedings of the Research in Computational Molecular Biology - 20th Annual Conference, 2016

On using Longer RNA-seq Reads to Improve Transcript Prediction Accuracy.
Proceedings of the 9th International Joint Conference on Biomedical Engineering Systems and Technologies (BIOSTEC 2016), 2016

Identification of Variant Compositions in Related Strains Without Reference.
Proceedings of the Algorithms for Computational Biology - Third International Conference, 2016

2015
Explaining a Weighted DAG with Few Paths for Solving Genome-Guided Multi-Assembly.
IEEE ACM Trans. Comput. Biol. Bioinform., 2015

Fast in-memory XPath search using compressed indexes.
Softw. Pract. Exp., 2015

Interval scheduling maximizing minimum coverage.
CoRR, 2015

Repeat- and error-aware comparison of deletions.
Bioinform., 2015

SNV-PPILP: refined SNV calling for tumor data using perfect phylogenies and ILP.
Bioinform., 2015

Diploid Alignments and Haplotyping.
Proceedings of the Bioinformatics Research and Applications - 11th International Symposium, 2015

Genome-Scale Algorithm Design: Biological Sequence Analysis in the Era of High-Throughput Sequencing.
Cambridge University Press, ISBN: 9781107078536, 2015

2014
Indexing Graphs for Path Queries with Applications in Genome Research.
IEEE ACM Trans. Comput. Biol. Bioinform., 2014

Towards the ground truth: Exact algorithms for bioinformatics research (NII Shonan Meeting 2014-2).
NII Shonan Meet. Rep., 2014

Multi-pattern matching with bidirectional indexes.
J. Discrete Algorithms, 2014

On the complexity of Minimum Path Cover with Subpath Constraints for multi-assembly.
BMC Bioinform., 2014

Editorial: Special Issue on Algorithms for Sequence Analysis and Storage.
Algorithms, 2014

2013
A novel min-cost flow method for estimating transcript expression with RNA-Seq.
BMC Bioinform., 2013

Haploid to diploid alignment for variation calling assessment.
BMC Bioinform., 2013

A Novel Combinatorial Method for Estimating Transcript Expression with RNA-Seq: Bounding the Number of Paths.
Proceedings of the Algorithms in Bioinformatics - 13th International Workshop, 2013

Versatile Succinct Representations of the Bidirectional Burrows-Wheeler Transform.
Proceedings of the Algorithms - ESA 2013, 2013

2012
Approximate all-pairs suffix/prefix overlaps.
Inf. Comput., 2012

Normalized N50 assembly metric using gap-restricted co-linear chaining.
BMC Bioinform., 2012

Indexed Multi-pattern Matching.
Proceedings of the LATIN 2012: Theoretical Informatics, 2012

Forbidden Patterns.
Proceedings of the LATIN 2012: Theoretical Informatics, 2012

Efficient Path Kernels for Reaction Function Prediction.
Proceedings of the BIOINFORMATICS 2012 - Proceedings of the International Conference on Bioinformatics Models, Methods and Algorithms, Vilamoura, Algarve, Portugal, 1, 2012

2011
Missing pattern discovery.
J. Discrete Algorithms, 2011

The Cycle Switching Graph of the Steiner Triple Systems of Order 19 is Connected.
Graphs Comb., 2011

Fast scaffolding with small independent mixed integer programs.
Bioinform., 2011

Indexing Finite Language Representation of Population Genotypes.
Proceedings of the Algorithms in Bioinformatics - 11th International Workshop, 2011

2010
Storage and Retrieval of Highly Repetitive Sequence Collections.
J. Comput. Biol., 2010

Filtering methods for content-based retrieval on indexed symbolic music databases.
Inf. Retr., 2010

Pattern Kits
CoRR, 2010

Unified View of Backward Backtracking in Short Read Mapping.
Proceedings of the Algorithms and Applications, 2010

2009
Efficient construction of maximal and minimal representations of motifs of a string.
Theor. Comput. Sci., 2009

Faster entropy-bounded compressed suffix trees.
Theor. Comput. Sci., 2009

Engineering a compressed suffix tree implementation.
ACM J. Exp. Algorithmics, 2009

Fast In-Memory XPath Search over Compressed Text and Tree Indexes
CoRR, 2009

2008
Point Pattern Matching.
Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Compressed Text Indexing.
Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Compressed Suffix Array.
Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Combinatorial Approaches for Mass Spectra Recalibration.
IEEE ACM Trans. Comput. Biol. Bioinform., 2008

Dynamic entropy-compressed sequences and full-text indexes.
ACM Trans. Algorithms, 2008

Run-Length Compressed Indexes Are Superior for Highly Repetitive Sequence Collections.
Proceedings of the String Processing and Information Retrieval, 2008

Fast Index Based Filters for Music Retrieval.
Proceedings of the ISMIR 2008, 2008

Space Efficient String Mining under Frequency Constraints.
Proceedings of the 8th IEEE International Conference on Data Mining (ICDM 2008), 2008

On Self-Indexing Images - Image Compression with Added Value.
Proceedings of the 2008 Data Compression Conference (DCC 2008), 2008

Storage and Retrieval of Individual Genomes.
Proceedings of the Structure-Based Compression of Complex Massive Data, 22.06., 2008

An In-Memory XQuery/XPath Engine over a Compressed Structured Text Representation.
Proceedings of the Structure-Based Compression of Complex Massive Data, 22.06., 2008

An(other) Entropy-Bounded Compressed Suffix Tree.
Proceedings of the Combinatorial Pattern Matching, 19th Annual Symposium, 2008

2007
Rank and select revisited and extended.
Theor. Comput. Sci., 2007

Compressed representations of sequences and full-text indexes.
ACM Trans. Algorithms, 2007

Rotation and lighting invariant template matching.
Inf. Comput., 2007

Compressed full-text indexes.
ACM Comput. Surv., 2007

Compressed suffix tree - a basis for genome-scale sequence analysis.
Bioinform., 2007

Implicit Compression Boosting with Applications to Self-indexing.
Proceedings of the String Processing and Information Retrieval, 2007

Space-Efficient Algorithms for Document Retrieval.
Proceedings of the Combinatorial Pattern Matching, 18th Annual Symposium, 2007

2006
A Simple Alphabet-independent Fm-index.
Int. J. Found. Comput. Sci., 2006

Flexible Music Retrieval in Sublinear Time.
Int. J. Found. Comput. Sci., 2006

Position-Restricted Substring Searching.
Proceedings of the LATIN 2006: Theoretical Informatics, 2006

2005
Succinct Suffix Arrays based on Run-Length Encoding.
Nord. J. Comput., 2005

On minimizing pattern splitting in multi-track string matching.
J. Discrete Algorithms, 2005

Transposition invariant string matching.
J. Algorithms, 2005

A simple alphabet-independent FM-index.
Proceedings of the Prague Stringology Conference, 2005

Maximum line-pair stabbing problem and its variations.
Proceedings of the (Informal) Proceedings of the 21st European Workshop on Computational Geometry, 2005

2004
Finding Missing Patterns.
Proceedings of the Algorithms in Bioinformatics, 4th International Workshop, 2004

First Huffman, Then Burrows-Wheeler: A Simple Alphabet-Independent FM-Index.
Proceedings of the String Processing and Information Retrieval, 2004

An Alphabet-Friendly FM-Index.
Proceedings of the String Processing and Information Retrieval, 2004

Advantages of Backward Searching - Efficient Secondary Memory and Distributed Implementation of Compressed Suffix Arrays.
Proceedings of the Algorithms and Computation, 15th International Symposium, 2004

Compressed Compact Suffix Arrays.
Proceedings of the Combinatorial Pattern Matching, 15th Annual Symposium, 2004

2003
Compact Suffix Array - A Space-Efficient Full-Text Index.
Fundam. Informaticae, 2003

Approximate Matching of Run-Length Compressed Strings.
Algorithmica, 2003

Matching Numeric Strings under Noise.
Proceedings of the Prague Stringology Conference 2003, Prague, Czech Republic, 2003

Algorithms for Transposition Invariant String Matching.
Proceedings of the STACS 2003, 20th Annual Symposium on Theoretical Aspects of Computer Science, Berlin, Germany, February 27, 2003

Geometric algorithms for transposition invariant content based music retrieval.
Proceedings of the ISMIR 2003, 2003

The C-BRAHMS project.
Proceedings of the ISMIR 2003, 2003

Sweepline the Music!
Proceedings of the Computer Science in Perspective, Essays Dedicated to Thomas Ottmann, 2003

2002
Local Similarity Based Point-Pattern Matching.
Proceedings of the Combinatorial Pattern Matching, 13th Annual Symposium, 2002

2001
Using Edit Distance in Point-Pattern Matching.
Proceedings of the Eighth International Symposium on String Processing and Information Retrieval, 2001

Trade Off Between Compression and Search Times in Compact Suffix Array.
Proceedings of the Algorithm Engineering and Experimentation, Third International Workshop, 2001

2000
Compact Suffix Array.
Proceedings of the Combinatorial Pattern Matching, 11th Annual Symposium, 2000


  Loading...