Recent Selected Publications

• Ahmed Sobih, Alexandru I. Tomescu, Veli Mäkinen, MetaFlow: Metagenomic profiling based on whole-genome coverage analysis with min-cost flows, To appear in Proc. of RECOMB 2016 [Preprint of extended version] [Implementation]
• Alexandru I. Tomescu, Paul Medvedev, Safe and complete contig assembly via omnitigs, To appear in Proc. of RECOMB 2016 [Preprint of extended version] [Implementation]
• Ademir Hujdurović, Urša Kačar, Martin Milanič, Bernard Ries, Alexandru I. Tomescu. Finding a perfect phylogeny from mixed tumor samples. In Proc. WABI 2015, LNCS 9289, pp. 80-92, 2015. [Article online] [Preprint of extended version]
• Martin D. Muggli, Simon J. Puglisi, Roy Ronen, Christina Boucher. Misassembly detection using paired-end sequence reads and optical mapping data. Bioinformatics 31(12):i80-i88, 2015 (ISMB 2015 Proceedings). [Implementation]
• 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]
• 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] [Preprint]
• Travis Gagie and Simon J. Puglisi, Searching and indexing genomic databases via kernelization, Frontiers in Bioengineering and Biotechnology, 3(12) (2015)
• Leena Salmela, Kristoffer Sahlin, Veli Mäkinen, and Alexandru I. Tomescu. Gap Filling as Exact Path Length Problem.
  In Proc. RECOMB 2015, LNCS 9029, pp. 281-292. [Implementation]
• Karen E. van Rens, Veli Mäkinen, and Alexandru Tomescu. SNV-PPILP: Refined SNV calling for tumor data using perfect phylogenies and ILP. Bioinformatics, 31(7):1133-1135, 2015. [Article online]
• Djamal Belazzougui, Travis Gagie, Simon Gog, Giovanni Manzini and Jouni Siren. Relative FM-indexes. In Proc. SPIRE 2014.
• Fabio Cunial and Djamal Belazzougui. Indexed matching statistics and shortest unique substrings. In Proc. SPIRE 2014.
• Veli Mäkinen and Daniel Valenzuela. Recombination-aware alignment of diploid individuals. BMC Genomics (RECOMB-CG 2014 supplement).
• Djamal Belazzougui. Linear time construction of compressed text indices in compact space. In Proc. STOC 2014, pp. 148-193.
• Héctor Ferrada, Travis Gagie, Tommi Hirvola and Simon J. Puglisi, Hybrid indexes for repetitive datasets, Philosophical Transactions of the Royal Society A, Volume 372, (2014).
• Travis Gagie, Pawel Gawrychowski, Juha Kärkkäinen, Yakov Nekrich, and Simon J. Puglisi. LZ77-Based Self-indexing with Faster Pattern Matching. In Proc. LATIN 2014, pp. 731-742.
• Romeo Rizzi, Alexandru I. Tomescu, and Veli Mäkinen. On the Complexity of Minimum Path Cover with
  Subpath Constraints for Multi-Assembly. BMC Bioinformatics (RECOMB-seq 2014 supplement).
• 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]
• Veli Mäkinen and Jani Rahkola. Haploid to Diploid Alignment for Variation Calling Assessment. BMC Bioinformatics 14(Suppl 15):S13 (15 October 2013). Presented at RECOMB-CG 2013.
  [Implementation]
• Alexandru I. Tomescu, Anna Kuosmanen, Romeo Rizzi and Veli 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]
• Travis Gagie, Danny Hermelin, Gad M. Landau and Oren Weimann. Binary Jumbled Pattern Matching on Trees and Tree-Like Structures. In Proc. ESA 2013, Springer, LNCS 8125, pp. 517-528, 2013.
  [Article online]
• Djamal Belazzougui, Fabio Cunial, J. 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]
• Travis Gagie, Kalle Karhu, Gonzalo Navarro, Simon Puglisi, and Jouni Sirén. Document Listing in Repetitive Collections. In Proc. CPM 2013. Springer, LNCS 7922, pp. 107-119, 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, April 11-12, 2013, Beijing, China, BMC Bioinformatics, 14(Suppl 5):S15 (10 April 2013).
  [Article online] 
  [Slides]
  [Implementation]
• 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]
• Niko Välimäki, and Simon J. Puglisi: Distributed String Mining for High-Throughput Sequencing Data.
  In Proc. 12th International Workshop on Algorithms in Bioinformatics (WABI 2012), Springer, LNCS 7534, pp. 441-452, 2012.
  [Article online]
• 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]
• Niko Välimäki: Least Random Suffix/Prefix Matches in Output-Sensitive Time.
  In Proc. 23rd Annual Symposium on Combinatorial Pattern Matching (CPM 2012), Springer,
  LNCS 7354, pp. 269-279, 2012.
  [Article online]
• 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]
• 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]
• 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.
  [Preprint]
• 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]
• Jouni Sirén, Niko Välimäki, and Veli Mäkinen: Indexing Finite Language Representation of Population Genotypes.
  In Proc. WABI 2011, Saarbrücken, Germany, September 5-7, 2011.
  [Article online]
  [Full version]
  [Implementation]
• See the listing at SuDS group for earlier publications