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 sets of k-long DNA sequences Rayan Chikhi, Jan Holub, and Paul Medvedev [ preprint ]

Scalable multiple whole-genome alignment and locally collinear block construction with SibeliaZ Ilia Minkin and Paul Medvedev [ preprint ]

Improved Representation of Sequence Bloom Trees Robert S. Harris and Paul Medvedev Bioinformatics, accepted.
[ journal version, equivalent preprint ]

Dosage regulation, and variation in gene expression and copy number at human Y chromosome ampliconic genes Rahul Vegesna, Marta Tomaszkiewicz, Paul Medvedev‡, and Kateryna Makova‡ PLOS Genetics, accepted

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‡ Transcation on Algorithms, accepted.
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 ]

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

DiscoverY: A classifier for identifying Y chromosome sequences in male assemblies Samarth Rangavittal, Natasha Stopa, Marta Tomaszkiewicz, Kristoffer Sahlin, Kateryna D. Makova‡, and Paul Medvedev‡ BMC Genomics , 2019, 20:641.
[ paper ]

De novo clustering of long-read transcriptome data using a greedy, quality-value based algorithm Kristoffer Sahlin and Paul Medvedev RECOMB 2019, accepted.
[ preprint]

Parallel Read Partitioning for Concurrent Assembly of Metagenomic Data Vasudevan Rengasamy, Mahmut Kandemir, Paul Medvedev and Kamesh Madduri HIPC 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, 2018.
[ preprint ]

Bipartite Graphs of Small Readability R. Chikhi, V. Jovicic, S. Kratsch, P. Medvedev, M. Milanic, S. Raskhodnikova and N. Varma Theretical Computer Science, accepted.
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, 2018, 1–8
[ paper ]

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 RECOMB, 2016.
[ 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, May 2014.
[ 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 ]