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.
The theoretical analysis of sequencing bioinformatics algorithms
Paul Medvedev
[ slides and paper draft ]
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.
[ preprint ]
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, accepted.
[ preprint ]
Error correction enables use of Oxford Nanopore technology for reference-free transcriptome analysis
Kristoffer Sahlin*, Botond Sipos*, Phillip L James, and Paul Medvedev
[ preprint ]
Representation of k-mer sets using spectrum-preserving string sets
Amatur Rahman and and Paul Medvedev
RECOMB 2020, LNCS 12074:152-168. (Best Paper Award)
[ preprint ]
Data structures to represent a set of k-long DNA sequences
Rayan Chikhi, Jan Holub, and Paul Medvedev
ACM Computing Surveys, accepted.
[ preprint ]
Scalable multiple whole-genome alignment and locally collinear block construction with SibeliaZ
Ilia Minkin and Paul Medvedev
Nature Communications, accepted.
[ preprint ]
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, evaa088, 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
Theretical 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, 2018, 1–8
[ 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 ]