Publications

Joint first authors are indicated with (*). Joint last 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.

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 RECOMB 2021, accepted.
[ 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, 2020
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 (alphabetical) 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č (alphabetical) 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č (alphabetical) 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 (alphabetical) Bioinformatics:25(21):2863-2864, 2009
[ paper ]

Rearrangement models and single-cut operations Anne Bergeron, Paul Medvedev, and Jens Stoye (alphabetical) 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 (alphabetical) 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 ]