Publications

Joint first authors are indicated with (*). Joint last authors are indicated with (‡). Alphabetically ordered authors are indicated with (†) . Please do not hesitate to e-mail me for a copy of a paper if your institution does not provide you access. You can also check my publications through DBLP or Google scholar.

Efficiency of Learned Indexes on Genome Spectra Md. Hasin Abrar†, Paul Medvedev†, Giorgio Vinciguerra† ESA 2025, accepted

K-mer-based estimators of the substitution rate between repetitive sequences Haonan Wu, Antonio Blanca‡ and Paul Medvedev‡ WABI 2025, accepted.

Estimation of substitution and indel rates via k-mer statistics Mahmudur Rahman Hera, Paul Medvedev, David Koslicki and Antonio Blanca WABI 2025, accepted.

Constructing and personalizing population pangenome graphs Rayan Chikhi, Yoann Dufresne, and Paul Medvedev Nature Methods, 21:1980–-1981, 2024.
(This is a News & Views article)
[ paper ]

PLA-index: A k-mer Index Exploiting Rank Curve Linearity Md. Hasin Abrar and Paul Medvedev Proceedings of WABI 2024, LIPIcs volume 312, pp. 13:1-13:18.
[ paper ]

The omnitig framework can improve genome assembly contiguity in practice Sebastian Schmidt, Santeri Toivonen, Paul Medvedev‡, and Alexandru I. Tomescu‡ Proceedings of WABI 2024, LIPIcs volume 312, pp. 8:1-8:16.
[ paper ]

The complete sequence and comparative analysis of ape sex chromosomes Makova et al. Nature, 630:401–-411, 2024.
[ paper ]

Fast Context-Aware Analysis of Genome Annotation Colocalization Askar Gafurov, Tomas Vinar, Paul Medvedev, and Brona Brejova Journal of Computational Biology, 31(10):946–964,2024.
A preliminary version appeared in RECOMB 2024, LNCS 14758:38–53.
[ paper ]

The complete sequence of a human Y chromosome Rhie et al. Nature, 621:344–354, 2023.
[ paper ]

Theoretical analysis of edit distance algorithms: an applied perspective Paul Medvedev Communications of the ACM, 66(12):64-71, 2023.
[ paper ]

The theoretical analysis of sequencing bioinformatics algorithms and beyond Paul Medvedev Communications of the ACM, 66(7):118-125, 2023.
[ paper ]

GPU-accelerated and pipelined methylation calling Y Feng, G G Akbulut, X Tang, J R Gunasekaran, A Rahman, P Medvedev, and M Kandemir Bioinformatics Advances, 2(1):vbac088, 2022.
[ paper ]

Exact sketch-based read mapping Tizian Schulz and Paul Medvedev Algorithms for Molecular Biology, 19:19, 2024.
An extended abstract appeared in WABI 2023, LIPIcs 273:14:1–14:19.
Note: The journal version (linked below) improves the memory to subquadratic, compared to the quadratic memory of the WABI version.
[ paper ]

Compression algorithm for colored de Bruijn graphs Amatur Rahman, Yoann Dufresne, Paul Medvedev Algorithms for Molecular Biology, 19:20, 2024.
An extended abstract appeared in WABI 2023, LIPIcs 273:17:1–17:14.
[ paper ]

Transcript isoform diversity of ampliconic genes on the Y chromosome of great apes Marta Tomaszkiewicz, Kristoffer Sahlin, Paul Medvedev‡, and Kateryna D. Makova‡ Genome Biology and Evolution, 15(11), evad205, 2023.
[ paper ]

Efficient mapping of accurate long reads in minimizer space with mapquik Barış Ekim, Kristoffer Sahlin, Paul Medvedev, Bonnie Berger, and Rayan Chikhi Proceedings of RECOMB 2023, Genome Research 33:1188–1197, 2023.
[ paper ]

Mapping-friendly sequence reductions: going beyond homopolymer compression Luc Blassel, Paul Medvedev, and Rayan Chikhi Proceedings of RECOMB-seq 2022.
iScience, 25:105305, 2022.
[ paper ]

Whole-genome sequence and assembly of the Javan gibbon (Hylobates moloch) Merly Escalona, …, Paul Medvedev, … et al. Journal of Heredity, esac043 2022.
[ paper ]

Assembler artifacts include misassembly because of unsafe unitigs and under-assembly because of bidirected graphs Amatur Rahman and Paul Medvedev Genome Research, 32:1-8, 2022.
An abstract appeared in RECOMB 2022, LNCS 13278:377–379.
[ paper (free version), paper (journal version) ]

The K-mer File Format: a standardized and compact disk representation of sets of k-mers Y. Dufresne, T. Lemane, P. Marijon, P. Peterlongo, A. Rahman, M. Kokot, P. Medvedev, S. Deorowicz, and R. Chikhi Bioinformatics, btac528, 2022.
[ paper ]

kmtricks: Efficient construction of Bloom filters for large sequencing data collections Téo Lemane, Paul Medvedev, Rayan Chikhi, and Pierre Peterlongo Bioinformatics Advances, vbac029, 2022.
[ paper ]

Markov chains improve the significance computation of overlapping genome annotations Askar Gafurov, Brona Brejova, and Paul Medvedev Proceedings of ISMB 2022, Bioinformatics 38 (Supplement_1): i203–i211.
[ paper, video ]

The minimizer Jaccard estimator is biased and inconsistent Mahdi Belbasi†, Antonio Blanca†, Robert S. Harris†, David Koslicki†, and Paul Medvedev† Proceedings of ISMB 2022, Bioinformatics 38 (Supplement_1): i169–i176.
[ paper, talk, slides ]

Recombination Marks the Evolutionary Dynamics of a Recently Endogenized Retrovirus Lei Yang, Raunaq Malhotra, Rayan Chikhi, Daniel Elleder, Theodora Kaiser, Jesse Rong, Paul Medvedev, and Mary Poss Molecular Biology and Evolution, 38(12):5423–5436, 2021.
[ paper ]

GYAN: Accelerating Bioinformatics Tools in Galaxy with GPU-Aware Computation Mapping G. Gudukbay, J.R. Gunasekaran, Y. Feng, M. Kandemir, A. Nekrutenko, C.R. Das, P. Medvedev, B. Gruning, N. Coraor, N. Roach, and E. Afgan IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW), 194–203, 2021.
[ paper ]

What do Eulerian and Hamiltonian cycles have to do with genome assembly? Paul Medvedev and Mihai Pop PLoS Computational Biology, 17(5):e1008928, 2021.
[ paper ]

Towards complete and error-free genome assemblies of all vertebrate species Rhie et al. Nature, 592:737–746, 2021.
[ paper ]

Data structures to represent a set of k-long DNA sequences Rayan Chikhi, Jan Holub, and Paul Medvedev ACM Computing Surveys, 54(1), 2021.
[ journal, equivalent preprint ]

The statistics of k-mers from a sequence undergoing a simple mutation process without spurious matches Antonio Blanca†, Robert S. Harris†, David Koslicki†, Paul Medvedev† Journal of Computational Biology, 29(2):155-168, 2022
An extended abstract appeared in RECOMB 2021.
[ full paper, latest slides , talk ]

Data structures based on k-mers for querying large collections of sequencing datasets Camille Marchet, Christina Boucher, Simon J Puglisi, Paul Medvedev, Mikaël Salson, Rayan Chikhi Genome Research, 31: 1-12, 2021.
[ journal version, equivalent preprint]

Error correction enables use of Oxford Nanopore technology for reference-free transcriptome analysis Kristoffer Sahlin and Paul Medvedev Nature Communications, 12(2), 2021.
[ paper ]

Disk Compression of k-mer Sets Amatur Rahman, Rayan Chikhi, and Paul Medvedev Algorithms for Molecular Biology, 16(10), 2021.
An extended abstract appeared in WABI 2020, LIPIcs 16:1–16:18.
[ full version (journal), conference ]

Scalable Pairwise Whole-Genome Homology Mapping of Long Genomes with BubbZ Ilia Minkin and Paul Medvedev Proceedings of RECOMB-seq 2020, iScience, 23(6): 101224, 2020.
[ paper ]

Ten Simple Rules for writing algorithmic bioinformatics conference papers Paul Medvedev PLOS Computational Biology, 16(4): e1007742, 2020.
[ paper ]

Dynamic evolution of great ape Y chromosomes M. Cechova*, R. Vegesna*, M. Tomaszkiewicz, R. S. Harris, D. Chen, S. Rangavittal, P. Medvedev‡, K. Makova‡ Proceedings of the National Academy of Sciences, 117(42):26273-26280, 2020.
[ paper ]

Representation of k-mer sets using spectrum-preserving string sets Amatur Rahman and and Paul Medvedev Journal of Computational Biology, 28(4):381-394, 2021.
An extended abstract appeared in RECOMB 2020, LNCS 12074:152-168. (Best Paper Award)
[ full version ]

Scalable multiple whole-genome alignment and locally collinear block construction with SibeliaZ Ilia Minkin and Paul Medvedev Nature Communications, 11 (6327), 2020.
[ paper ]

Improved Representation of Sequence Bloom Trees Robert S. Harris and Paul Medvedev Bioinformatics, 36(3): 721–727, 2020.
[ journal version, equivalent preprint ]

Ampliconic genes on the great ape Y chromosomes: Rapid evolution of copy number but conservation of expression levels R. Vegesna*, M. Tomaszkiewicz*, O. A. Ryder, R. Campos-Sánchez, P. Medvedev, M. DeGiorgio‡, K. D. Makova‡ Genome Biology and Evolution, 12(6):842–859, 2020.
[ paper ]

Dosage regulation, and variation in gene expression and copy number at human Y chromosome ampliconic genes Rahulsimham Vegesna, Marta Tomaszkiewicz, Paul Medvedev‡, and Kateryna Makova‡ PLOS Genetics, 15(9):e1008369, 2019.
[ paper ]

An optimal O(nm) algorithm enumerating all walks common to all closed edge-covering walks of a graph Massimo Cairo, Paul Medvedev, Nidia Obscura Acosta, Romeo Rizzi‡, and Alexandru I. Tomescu‡ ACM Transactions on Algorithms, 15(4): 48, 2019.
An extended abstract appeared in CPM 2017, LIPIcs, 78:29:1-12, under the title “Optimal Omnitig Listing for Safe and Complete Contig Assembly”
[ conference version, journal version ]

DiscoverY: A classifier for identifying Y chromosome sequences in male assemblies S. Rangavittal, N. Stopa, M. Tomaszkiewicz, K. Sahlin, K. D. Makova‡, and P. Medvedev‡ BMC Genomics , 20:641, 2019.
[ paper ]

De novo clustering of long-read transcriptome data using a greedy, quality-value based algorithm Kristoffer Sahlin and Paul Medvedev Journal of Computational Biology, 27(4): 472–484, 2020.
An extended abstract appeared in RECOMB 2019, LNCS 11467:227-242.
[ full version]

Parallel Read Partitioning for Concurrent Assembly of Metagenomic Data Vasudevan Rengasamy, Mahmut Kandemir, Paul Medvedev and Kamesh Madduri IEEE 25th International Conference on High Performance Computing (HiPC), 324-333, 2018.
[ paper ]

Deciphering highly similar multigene family transcripts from Iso-Seq data with IsoCon Kristoffer Sahlin*, Marta Tomaszkiewicz*, Kateryna D. Makova‡, Paul Medvedev‡ Nature Communications, 2018, 9:4601.
[ journal, bioRxiv (with easier to read Methods) ]

Correcting palindromes in long reads after whole-genome amplification S. Warris, E. Schijlen, H. van de Geest, R. Vegesna, T. Hesselink, B. te Lintel Hekkert, G. Sanchez-Perez, P. Medvedev, K.D. Makova, D. de Ridder BMC Genomics, 19(1):798, 2018.
[ preprint ]

Toward fast and accurate SNP genotyping from whole genome sequencing data for bedside diagnostics Chen Sun and Paul Medvedev Bioinformatics, 35(3):415-420, 2019.
[ preprint ]

Bipartite Graphs of Small Readability R. Chikhi, V. Jovicic, S. Kratsch, P. Medvedev, M. Milanic, S. Raskhodnikova and N. Varma Theoretical Computer Science, 806:402-415, 2020.
An extended abstract appeared in COCOON 2018, LNCS 10976:467-479.
[ full version, conference version ]

Modeling Biological Problems in Computer Science: A Case Study in Genome Assembly Paul Medvedev Briefings in Bioinformatics, 20(4):1376-1383, 2019.
[ paper, slides ]

RecoverY: K-mer based read classification for Y-chromosome specific sequencing and assembly S. Rangavittal, R. S. Harris, M. Cechova, M. Tomaszkiewicz, R. Chikhi, K. D. Makova‡, and P. Medvedev‡ Bioinformatics, 2017.
[ paper ]

Parallel and Memory-efficient Preprocessing for Metagenome Assembly Vasudevan Rengasamy, Paul Medvedev and Kamesh Madduri HiCOMB 2017.
[ paper (via journal), pdf ]

Y and W Chromosome Assemblies: Approaches and Discoveries Marta Tomaszkiewicz, Paul Medvedev, Kateryna D. Makova Trends in Genetics, 2017.
[ paper (via journal), pdf ]

AllSome Sequence Bloom Trees Chen Sun*, Robert S. Harris*, Rayan Chikhi and Paul Medvedev Journal of Computational Biology, 25(5): 467–479, 2018.
An extended abstract appeared in RECOMB 2017, LNCS 10229:272-286.
[ bioRxiv ]

VarMatch: robust matching of small variant datasets using flexible scoring schemes Chen Sun and Paul Medvedev Bioinformatics, 2016.
[ bioRxiv ]

TwoPaCo: An efficient algorithm to build the compacted de Bruijn graph from many complete genomes Ilia Minkin, Son Pham, and Paul Medvedev Bioinformatics 2016.
[ paper, poster, slides ]

Computational Pan-Genomics: Status, Promises and Challenges Tobias Marschall, …. Paul Medvedev …. et al Briefings in Bioinformatics, 2016.
[ preprint ]

Compacting de Bruijn graphs from sequencing data quickly and in low memory Rayan Chikhi, Antoine Limasset and Paul Medvedev Proceedings of ISMB 2016, Bioinformatics, 32 (12): i201-i208.
[ paper ]

Giraffe genome sequence reveals clues to its unique morphology and physiology M Agaba, E Ishengoma, W C. Miller, B C. McGrath, C Hudson, O C. Bedoya Reina, A Ratan, R Burhans, R Chikhi, P Medvedev, C A. Praul, L Wu-Cavener, B Wood, H Robertson, L Penfold, and D R. Cavener Nature Communications, 7:11519, 2016.
[ paper ]

A time- and cost-effective strategy to sequence mammalian Y chromosomes: an application to the de novo assembly of gorilla Y M. Tomaszkiewicz*, S. Rangavitta*, M. Cechova*, R. C. Sanchez, H. W. Fescemyer, R. Harris, D. Ye, P. C. M. O’Brien, R. Chikhi, O. Ryder, M. A. Ferguson-Smith, P. Medvedev‡, and K. D. Makova‡ Genome Research, 2016.
[ paper ]

Safe and complete contig assembly via omnitigs Alexandru I. Tomescu and Paul Medvedev Journal of Computational Biology, 25(5): 467–479, 2018.
An extended abstract appeared in RECOMB 2016, LNCS 9649:152-163.
[ full version ]

On the readability of overlap digraphs Rayan Chikhi†, Paul Medvedev†, Martin Milanič†, and Sofya Raskhodnikova† Discrete Applied Mathematics, 205: 35-44, 2016.
An extended abstract appeared in CPM 2015, LNCS 9133:124-137.
[ full version ]

Improving the power of structural variation detection by augmenting the reference Jan Schröder, Santhosh Girirajan, Anthony T. Papenfuss, Paul Medvedev PLoS ONE, 10(8): e0136771, 2015.
[ paper ]

Accurate typing of short tandem repeats from genome-wide sequencing data and its applications Arkarachai Fungtammasan, Guruprasad Ananda, Suzanne E. Hile, Marcia Shu-Wei Su, Chen Sun, Robert Harris, Paul Medvedev‡, Kristin Eckert‡ and Kateryna D. Makova‡ Genome Research, 25: 736-749, 2015.
[ paper ]

A combinatorial approach to the design of vaccines Luis Martínez, Martin Milanič, Leire Legarreta, Paul Medvedev, Iker Malaina, M Ildefonso Journal of Mathematical Biology, 70:1327–1358 ,2015.
[ paper ]

On the representation of de Bruijn graphs Rayan Chikhi, Antoine Limasset, Shaun Jackman, Jared T. Simpson, and Paul Medvedev Journal of Computational Biology, 22(5): 336-352, 2015.
An extended abstract appeared in RECOMB 2014, LNCS 8394:35-55.
[ updated arXiv, conference version, ]

Informed and automated k-mer size selection for genome assembly Rayan Chikhi and Paul Medvedev High Throughput Sequencing Methods and Applications (HiTSeq), special interest group of ISMB 2013, Bioinformatics (2014) 30 (1): 31-37. (Best Paper Award)
[ paper ]

Using state machines to model the IonTorrent sequencing process and improve read error-rates David Golan and Paul Medvedev Proceedings of ISMB 2013, Bioinformatics (2013) 29 (13): i344-i351.
[ paper ]

Resolving low-copy duplicated sequences using template driven assembly Sangwoo Kim, Paul Medvedev, Tara Paton, and Vineet Bafna Nucleic Acids Research (2013) 41 (12): e128.
[ paper ]

Error correction of high-throughput sequencing datasets with non-uniform coverage Paul Medvedev, Eric Scott, Boyko Kakaradov, and Pavel Pevzner Proceedings of ISMB 2011, Bioinformatics (2011) 27 (13): i137-i141.
[ paper ]

Paired de Bruijn graphs: a novel approach for incorporating mate pair information into genome assemblers Paul Medvedev*, Son Pham*, Mark Chaisson, Glenn Tesler and Pavel Pevzner Journal of Computational Biology, 18(11): 1625-1634, 2011.
An extended abstract appeared in RECOMB 2011, LNCS 6577:238-251.
[ journal version, conference version ]

Complexity of independent set reconfigurability problems Marcin Kamiński†, Paul Medvedev† and Martin Milanič† Theoretical Computer Science, 439(29):9-15, 2012.
[ paper ] Note: Several results of this paper appeared in an extended abstract at International Workshop on Combinatorial Algorithms (IWOCA), LNCS 6460:55-67, 2010. [ here ]

Shortest paths between shortest paths Marcin Kamiński†, Paul Medvedev†, and Martin Milanič† Theoretical Computer Science, 412(39):5205-5210, 2011.
[ paper ] Note: Several results of this paper appeared in an extended abstract at International Workshop on Combinatorial Algorithms (IWOCA), LNCS 6460:55-67, 2010. [ here ]

Detecting copy number variation with mated short reads Paul Medvedev, Marc Fiume, Misko Dzamba, Tim Smith, Michael Brudno Genome Research, 20:1613-1622, 2010.
[ paper ]

Computational methods for discovering structural variation with next generation sequencing Paul Medvedev, Monica Stanciu, Michael Brudno Nature Methods, 6(11):S13-S20, 2009.
[ paper ]

A report on the 2009 SIG on short read sequencing and algorithms (Short-SIG) Michael Brudno†, Paul Medvedev†, Jens Stoye†, and Fransisco M. de la Vega† Bioinformatics:25(21):2863-2864, 2009
[ paper ]

Rearrangement models and single-cut operations Anne Bergeron†, Paul Medvedev†, and Jens Stoye† Journal of Computational Biology, 17(9):1213-1225, 2010.
An extended abstract appeared in RECOMB-CG, LNCS 5817:84-97, 2009.
[ journal version, conference version ]

The plane-width of graphs Marcin Kamiński†, Paul Medvedev† and Martin Milanič† Journal of Graph Theory, 68(3):229-245, 2011.
An extended abstract appeared in European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2009), ENDM 34 (2009) 633-637.
[ journal version, extended abstract ]

Maximum likelihood genome assembly Paul Medvedev and Michael Brudno Journal of Computational Biology, 16(8):1101-1116, 2009.
An extended abstract appeared in RECOMB 2008, LNCS 4955:50-64, under the title
“Ab initio whole genome shotgun assembly with mated short reads.”
[ journal version, conference version ]

Computability of models for sequence assembly Paul Medvedev, Konstaninos Georgiou, Gene Myers, and Michael Brudno Proceedings of WABI 2007, LNCS 4645:289-301.
[ paper ]

The relative worst order ratio applied to seat reservation Joan Boyar† and Paul Medvedev† ACM Transactions on Algorithms, 4(4):1-22, 2008.
An extended abstract appeared in SWAT 2004, LNCS 3111:90-101.
[ journal version, conference version ]

A self-coordinating approach to distributed fair queueing in ad hoc wireless networks Haiyun Luo, Paul Medvedev, Jerry Cheng and Songwu Lu Proceedings of IEEE INFOCOM 2001, 2001.
[ paper ]