Optimal Omnitig Listing for Safe and Complete Contig Assembly Massimo Cairo, Paul Medvedev, Nidia Obscura Acosta, Romeo Rizzi‡, and Alexandru I. Tomescu‡ CPM 2017, accepted.

Parallel and Memory-efficient Preprocessing for Metagenome Assembly Vasudevan Rengasamy, Paul Medvedev and Kamesh Madduri HiCOMB 2017, accepted.

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

AllSome Sequence Bloom Trees Chen Sun*, Robert S. Harris*, Rayan Chikhi and Paul Medvedev RECOMB, 2017.
[ 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 ]

Please do not hesiitate to e-mail me for a copy of a paper if your institution does not provide you access.

Joint first authors are indicated with (*).
Joint last authors are indicated with (‡).