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.

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 ]

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 WABI 2020, LIPIcs 16:1–16:18.
[ paper ]

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 ]