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.
Constructing and personalizing population pangenome graphs
Rayan Chikhi, Yoann Dufresne, and Paul Medvedev
Nature Methods, 2024.
(This is a News & Views article)
[ paper ]
PLA-complexity of k-mer multisets
Md. Hasin Abrar and Paul Medvedev
Proceedings of WABI 2024, LIPIcs volume 312, pp. 13:1-13:18.
[ paper ]
The omnitig framework can improve genome assembly contiguity in practice
Sebastian Schmidt, Santeri Toivonen, Paul Medvedev‡, and Alexandru I. Tomescu‡
Proceedings of WABI 2024, LIPIcs volume 312, pp. 8:1-8:16.
[ paper ]
The complete sequence and comparative analysis of ape sex chromosomes
Makova et al.
Nature, 630:401–-411, 2024.
[ paper ]
Efficient analysis of annotation colocalization accounting for genomic contexts
Askar Gafurov, Tomas Vinar, Paul Medvedev, and Brona Brejova
RECOMB 2024, accepted.
[ paper ]
The complete sequence of a human Y chromosome
Rhie et al.
Nature, 621:344–354, 2023.
[ paper ]
Theoretical analysis of edit distance algorithms: an applied perspective
Paul Medvedev
Communications of the ACM, 66(12):64-71, 2023.
[ paper ]
The theoretical analysis of sequencing bioinformatics algorithms and beyond
Paul Medvedev
Communications of the ACM, 66(7):118-125, 2023.
[ paper ]
GPU-accelerated and pipelined methylation calling
Y Feng, G G Akbulut, X Tang, J R Gunasekaran, A Rahman, P Medvedev, and M Kandemir
Bioinformatics Advances, 2(1):vbac088, 2022.
[ paper ]
Exact sketch-based read mapping
Tizian Schulz and Paul Medvedev
Algorithms for Molecular Biology, 19:19, 2024.
An extended abstract appeared in WABI 2023, LIPIcs 273:14:1–14:19.
Note: The journal version (linked below) improves the memory to subquadratic, compared to the quadratic memory of the WABI version.
[ paper ]
Compression algorithm for colored de Bruijn graphs
Amatur Rahman, Yoann Dufresne, Paul Medvedev
Algorithms for Molecular Biology, 19:20, 2024.
An extended abstract appeared in WABI 2023, LIPIcs 273:17:1–17:14.
[ paper ]
Transcript isoform diversity of ampliconic genes on the Y chromosome of great apes
Marta Tomaszkiewicz, Kristoffer Sahlin, Paul Medvedev‡, and Kateryna D. Makova‡
Genome Biology and Evolution, 15(11), evad205, 2023.
[ paper ]
Efficient mapping of accurate long reads in minimizer space with mapquik
Barış Ekim, Kristoffer Sahlin, Paul Medvedev, Bonnie Berger, and Rayan Chikhi
Proceedings of RECOMB 2023, Genome Research 33:1188–1197, 2023.
[ paper ]
Mapping-friendly sequence reductions: going beyond homopolymer compression
Luc Blassel, Paul Medvedev, and Rayan Chikhi
Proceedings of RECOMB-seq 2022.
iScience, 25:105305, 2022.
[
paper
]
Whole-genome sequence and assembly of the Javan gibbon (Hylobates moloch)
Merly Escalona, …, Paul Medvedev, … et al.
Journal of Heredity, esac043 2022.
[ paper ]
Assembler artifacts include misassembly because of unsafe unitigs and under-assembly because of bidirected graphs
Amatur Rahman and Paul Medvedev
Genome Research, 32:1-8, 2022.
An abstract appeared in RECOMB 2022, LNCS 13278:377–379.
[
paper (free version),
paper (journal version)
]
The K-mer File Format: a standardized and compact disk representation of sets of k-mers
Y. Dufresne, T. Lemane, P. Marijon, P. Peterlongo, A. Rahman, M. Kokot, P. Medvedev, S. Deorowicz, and R. Chikhi
Bioinformatics, btac528, 2022.
[ paper ]
kmtricks: Efficient construction of Bloom filters for large sequencing data collections
Téo Lemane, Paul Medvedev, Rayan Chikhi, and Pierre Peterlongo
Bioinformatics Advances, vbac029, 2022.
[ paper ]
Markov chains improve the significance computation of overlapping genome annotations
Askar Gafurov, Brona Brejova, and Paul Medvedev
Proceedings of ISMB 2022, Bioinformatics 38 (Supplement_1): i203–i211.
[ paper, video ]
The minimizer Jaccard estimator is biased and inconsistent
Mahdi Belbasi, Antonio Blanca, Robert S. Harris, David Koslicki, and Paul Medvedev
Proceedings of ISMB 2022, Bioinformatics 38 (Supplement_1): i169–i176.
[ paper, talk, slides ]
Recombination Marks the Evolutionary Dynamics of a Recently Endogenized Retrovirus
Lei Yang, Raunaq Malhotra, Rayan Chikhi, Daniel Elleder, Theodora Kaiser, Jesse Rong, Paul Medvedev, and Mary Poss
Molecular Biology and Evolution, 38(12):5423–5436, 2021.
[ paper ]
GYAN: Accelerating Bioinformatics Tools in Galaxy with GPU-Aware Computation Mapping
G. Gudukbay, J.R. Gunasekaran, Y. Feng, M. Kandemir, A. Nekrutenko, C.R. Das, P. Medvedev, B. Gruning, N. Coraor, N. Roach, and E. Afgan
IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW), 194–203, 2021.
[ paper ]
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
Journal of Computational Biology, 29(2):155-168, 2022
An extended abstract appeared in RECOMB 2021.
[ 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, 28(4):381-394, 2021.
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 ]