comparative genomics on my daughter's animals

Everything interests me, but mostly I have been working on algorithmic and statistical problems in genomics, including molecular evolution (evolution of gene content, exon-intron structure, pseudogenes, and construction of large phylogenies), sequence analysis (homology search & segmentation), genome sequencing (clone mapping, genotyping, NGS applications) and other, more theoretical problems.

Google scholar profile: I keep it in tip-top shape by weeding out my daddy's nuclear physics publications like this one.

Software downloads and supporting webpages

Software

Quadgt logo QuadGT: genotype inference from mapped sequencing reads in four genomes
Count logo Count: gene family evolution and analysis of numerical phylogenetic profiles
Malin logo Malin: exon-intron structure evolution

Supporting webpages

Introns: http://www.iro.umontreal.ca/~csuros/introns/
Oligonucleotide frequencies/genomic spectrum:http://www.iro.umontreal.ca/~csuros/spectrum/

Molecular evolution

2013: Evolution of divergent life history strategies in marine Alphaproteobacteria. Haiwei Luo, Miklós Csűrös, Austin L. Hughes and Mary Ann Moran.
mBio, 4(4):e00373-13, 2013. doi: 10.1128/mBio.00373-13 (open access).
Evolution of gene repertoire in Roseobacter and SAR11 lineages of marine bacteria.
2013: How to infer ancestral genome features by parsimony: dynamic programming over an evolutionary tree. Miklós Csűrös.
A celebratory article about David Sankoff's pioneering work on dynamic programming.
Models and Algorithms for Genome Evolution, Cedric Chauve, Nadia El-Mabrouk and Eric Tannier, eds. Springer-Verlag, in print. 2013.
PDF. Preprint.
2013: Whence genes in pieces: reconstruction of the exon-intron gene structures of the last eukaryotic common ancestor and other ancestral eukaryotes. Eugene V. Koonin, Miklós Csűrös and Igor B. Rogozin.
[Review article]
WIREs RNA, 4:93-105, 2013. doi:10.1002/wrna.1143 (open access)
2012: Origin and evolution of spliceosomal introns Igor B. Rogozin, Liran Carmel, Miklós Csűrös and Eugene V. Koonin.
[Review article]
Biology Direct, 7:11, 2012. doi:10.1186/1745-6150-7-11 (open access).
2011: A detailed history of intron-rich eukaryotic ancestors inferred from a global survey of 100 complete genomes. Miklós Csűrös, Igor B. Rogozin and Eugene V. Koonin.
We reconstructed the history of intron gain and loss during the evolution of eukaryotes in a Markov Chain Monte Carlo estimation procedure applied to a set of 245 orthologous genes from 99 genomes that represent the entire known diversity of eukaryotes. The reconstruction shows that the ancestors of each of the major groups of eukaryotes were intron-rich. [...] The entire line of descent from LECA to mammals is reconstructed as a continuous intron-rich state, a condition that triggered evolution of nonsense-mediated decay and alternative splicing.
PLoS Computational Biology, 7(9):e1002150, 2011. doi:10.1371/journal.pcbi.1002150 (open access).
WWW Companion website - detailed plots about intron gains and losses in orthologous genes.
youtube logo Video on YouTube.
2011: A late origin of the extant eukaryotic diversity: divergence time estimates using rare genomic changes. Diana Chernikova, Sam Motamedi, Miklós Csűrös, Eugene V. Koonin and Igor B. Rogozin.
We applied the genome-wide analysis of rare genomic changes associated with conserved amino acids (RGC_CAs) and used several independent techniques to obtain date estimates for the divergence of the major lineages of eukaryotes. [...] If these estimates are valid, the billion years of evolution of eukaryotes that is open to comparative-genomic study probably was preceded by approximately the same duration of evolution that might have included extinct diversity inaccessible to comparative approaches.
Biology Direct, 6:26, 2011. doi:10.1186/1745-6150-6-26 (open access).
2010: Count: evolutionary analysis of phylogenetic profiles with parsimony and likelihood. Miklós Csűrös
[Application note] Count is a software package for the analysis of numerical profiles on a phylogeny. It is primarily designed to deal with profiles derived from the phyletic distribution of homologous gene families, but is suited to study any other integer-valued evolutionary characters. Count performs ancestral reconstruction, and infers family- and lineage-specific characteristics along the evolutionary tree. It implements popular methods employed in gene content analysis such as Dollo and Wagner parsimony, propensity for gene loss, as well as probabilistic methods involving a phylogenetic birth- and-death model.
Bioinformatics, 26(15):1910-1912, 2010. doi:10.1093/bioinformatics/btq315 (open access).
PDF Reprint from Oxford University Press.
PDF Preprint.
WWW Software download page
2009: Streamlining and large ancestral genomes in Archaea inferred with a phylogenetic birth-and-death model. Miklós Csűrös and István Miklós.
We describe here our framework of phylogenetic birth-and-death models, with an application to gene content evolution in Archaea: we think that LACA had many genes even by today's standards.
Molecular Biology and Evolution 26(9):2087-2095, 2009. doi:10.1093/molbev/msp123 (open access).
PDF Preprint.
2009: Mathematical framework for phylogenetic birth-and-death models. Miklós Csűrös and István Miklós.
A phylogenetic birth-and-death model is a probabilistic graphical model for a so-called phylogenetic profile, i.e., the size distribution for a homolog gene family at the terminal nodes of a phylogeny. Profile datasets are used in bioinformatics analyses for the inference of evolutionary trees, and of functional associations between gene families, as well as for the quantification of various processes guiding genome evolution. Here we describe the mathematical formalism for phylogenetic birth-and-death models. We also present an algorithm for computing the likelihood in a gain-loss-duplication model.
Manuscript.
q-bio.PE/0902.0970 Report at arXiv.
PDF. Preprint.
2009: Analysis of rare genomic changes does not support the unikont-bikont phylogeny and suggests cyanobacterial symbiosis as the point of primary radiation of eukaryotes. Igor B. Rogozin, Malay K. Basu, Miklós Csűrös and Eugene V. Koonin.
The title says it all.
Genome Biology and Evolution, doi:10.1093/gbe/evp011 (open access).
2008: Ancestral reconstruction by asymmetric Wagner parsimony over continuous characters and squared parsimony over distributions. Miklós Csűrös.
Asymmetric Wagner: parsimony analysis of a numerical character such as gene family size or genome length, using different gain and loss penalties. The analysis is applied to Archaeal gene content evolution using arCOGs. Also, squared parsimony can be solved in each dimension independently to get the optimal reconstruction for distributions such as allele frequencies or sequence motifs.
Sixth RECOMB Satellite Workshop on Comparative Genomics, 72-86. Springer LNBI 5267. doi:10.1007/978-3-540-87989-3_6.
PDF Preprint.
2008: Malin: maximum likelihood analysis of intron evolution in eukaryotes. Miklós Csűrös
[Application note] Malin is a software package for the analysis of eukaryotic gene structure evolution. It provides a graphical user interface for inferring intron gain and loss rates, loss and gain events in individual lineages, and ancestral intron content.
Bioinformatics, 24(13):1538-1539, 2008. doi:10.1093/bioinformatics/btn226 (open access).
PDF Preprint.
WWW Software download page
2008: Homoplasy in genome-wide analysis of rare amino acid replacements: the molecular-evolutionary basis for Vavilov's law of homologous series. Igor B. Rogozin, Karen Thomson, Miklós Csűrös, Liran Carmel and Eugene V. Koonin.
Parallel changes are more common between deep phylogenetic lineages. After accounting for homoplasy, RGC-CAMs support the coelomata hypothesis [flies are closer to us than to worms]. RGC-CAMs are rare genomic changes for amino acids conserved within separate taxonomic groups, where the change between groups involves multiple nucleotide substitutions at the codon level.
Biology Direct, 3:7, 2008. doi:10.1186/1745-6150-3-7 (open access).
2008: Extremely intron-rich genes in the alveolate ancestors inferred with a flexible maximum likelihood approach. Miklós Csűrös, Igor B. Rogozin and Eugene V. Koonin.
A rates-across-sites variation model for exon-intron structure evolution. Evolution of gene structure across 23 eukaryotes (11 chromalveolates, 5 plants/green algae, 7 animals/fungi): the intron density in the genes of the alveolate ancestor is estimated to be slightly greater than the human intron density.
Molecular Biology and Evolution, 25(5):903-911, 2008. doi:10.1093/molbev/msn039 (open access).
PDF Preprint.
WWW Supporting website - detailed plots about intron gains and losses in orthologous genes.
2007: In search of lost introns. Miklós Csűrös, J. Andrew Holey and Igor B. Rogozin.
Intron-aware multiple alignment and fast evaluation of the likelihood function.
Bioinformatics, 23(13):i87-i96, 2007. (Proceedings of ISMB/ECCB - Fifteenth Annual International Conference on Intelligent Systems for Molecular Biology & Sixth European Conference on Computational Biology.) doi:10.1093/bioinformatics/btm190 (open access).
WWW Supplementary material & software download page.
q-bio/0702005 Earlier version at arXiv.
2007: A glimpse of a putative pre-intron phase of eukaryotic evolution. Alexander V. Sverdlov, Miklós Csűrös, Igor B. Rogozin and Eugene V. Koonin.
Exon-intron structures between ancient eukaryotic paralogs show no similarity. Were the introns lost during duplication or were they not there to begin with?
Trends in Genetics, 23(3):105-108, 2007. doi:10.1016/j.tig.2007.01.001.
2006: On the estimation of intron evolution. Miklós Csűrös.
[Correspondence.] Posterior probabilities for ancestral states in a phylogeny can be computed in linear time.
PLoS Computational Biology, 2(7):e84, 2006. doi:10.1371/journal.pcbi.0020084 (open access).
2006: A probabilistic model for gene content evolution with duplication, loss, and horizontal transfer. Miklós Csűrös and István Miklós.
Three-parameter likelihood model for the evolution of gene family size: birth-and-death chains on a phylogeny.
RECOMB 2006 - Tenth Annual International Conference on Research in Computational Molecular Biology, 206-220, Springer LNBI 3909. doi:10.1007/11732990_18.
PDF Preprint.
q-bio/0509037 Earlier version at arXiv.
2005: Likely scenarios of intron evolution. Miklós Csűrös.
A maximum likelihood model for studying intron evolution: computing intron density, losses and gains for ancestral eukaryotes.
Third RECOMB Satellite Workshop on Comparative Genomics, 47-60, Springer LNCS 3678. doi:10.1007/11554714_5
PDF Preprint.
WWW Supplementary material & software download page.
2005: Statistical alignment of retropseudogenes and their functional paralogs. Miklós Csűrös and István Miklós.
Model and algorithms for alignment of a processed pseudogene and its protein-coding paralog; evolution of human cytochrome c.
Molecular Biology and Evolution, 22(12):2457-2471, 2005. doi:10.1093/molbev/msi238.
PDF Reprint from Oxford University Press.
PDF Supplementary material.
A short abstract of this paper was presented under the title Statistical alignment of retropseudogenes and their functional paralogs via a common ancestor at the 30th FEBS Congress & 9th IUBMB Conference, July 2-7, 2005. Abstract: FEBS Journal 272(s1) A3-029P.
2002: Fast recovery of evolutionary trees with thousands of nodes. Miklós Csűrös.
An O(n2) distance-based algorithm with polynomial sample lengths for phylogenetic reconstruction, without extra input parameters.
Journal of Computational Biology, 9(2): 277-297, 2002. doi:10.1089/10665270252935467.
PDF Preprint.
2001: Fast recovery of evolutionary trees with thousands of nodes. Miklós Csűrös.
Conference version of the above paper.
RECOMB 2001 - Fifth Annual International Conference on Computational Molecular Biology, 104-113, 2001. doi:10.1145/369133.369178.
PDF Preprint.
PDF Presentation.
2001: Provably fast and accurate recovery of evolutionary trees through Harmonic Greedy Triplets. Miklós Csűrös and Ming-Yang Kao.
First O(n2) distance-based algorithm with polynomial sample lengths for phylogenetic reconstruction.
SIAM Journal on Computing, 31(1): 306-322, 2001. doi:10.1137/S009753970037905X.
PDF Preprint.
1999: Recovering evolutionary trees through Harmonic Greedy Triplets. Miklós Csűrös and Ming-Yang Kao.
Conference version of the above paper.
SODA 1999 - Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 261-270.
PotScript Preprint.
2000: Reconstructing Phylogenies in Markov Models of Evolution. Miklós Csűrös.
Ph. D. dissertation, Department of Computer Science, Yale University.
PDF Summary.
PDF Full text.
PostScript Full text - with random illustrations generated on the printer!
Implementations of HGT and Fast-HGT algorithms.
Implementation in C, and a collection of Perl modules and scripts.

Missing files (HGT-ME and such): Those results are in the dissertation.

Sequencing, mapping and genotyping

2013: Ambiguous inference of identity coefficients from independent biallelic loci Miklós Csűrös.
Short of a complete pedigree, two individual's relatedness can be characterized by the frequency of identity-by-descent (IBD) modes, each corresponding to a combinatorially different pattern of allele dependencies. At a biallelic diploid locus, different mixtures of IBD modes can produce the same joint genotype distribution: IBD coefficients cannot be identified from the genotypes. On the basis of biallelic genotypes, the IBD structure can instead be unambiguously dissected into five components, including classic measures of kinship and inbreeding.
Manuscript.
PDF Preprint.
PDF Supporting Information.
2013: Joint genotype inference with germline and somatic mutations. Eric Bareke, Virginie Saillour, Jean-François Spinella, Ramon Vidal, Jasmine Healy, Daniel Sinnett and Miklós Csűrös.
Given sequencing reads for father, mother, child, and child's tumor, we assign genotypes by tracking somatic and de novo germline mutations, inheritance (autosomes, sex chromosomes, and mitochondria), sequencing errors and tumor sampling purity.
BMC Bioinformatics, 14(Suppl 5):S3, 2013. (Proceedings of RECOMB-SEQ 2013 -Third RECOMB Satellite Workshop on Massively Parallel Sequencing.) doi:10.1186/1471-2105-14-S5-S3 (open access).
WWW Software download page for QuadGT
2010: Fast mapping and precise alignment of AB SOLiD color reads to reference DNA. Miklós Csűrös, Szilveszter Juhos and Attila Bérces.
Color read mapping with greedy alignment (Wu, Manber, Myers, Miller), and statistical alignment with read quality values.
WABI 2010 - Tenth Workshop on Algorithms in Bioinformatics, 176-188, 2010. Springer LNBI 6293.
PDF Preprint.
commercial implementation from omixon
Genome projects
I had worked on hybrid (BAC-based+whole genome shotgun) sequence assembly methods that rely on the shotgun sequencing of BAC pools. The pooling-based approach can be used for de novo mapping (CAPS-MAP) and sequencing (CAPSS), or for comparative mapping (PGI). I participated in the rhesus macaque and honey bee genome projects, which used pooling. [See the list of Genbank entries I had a part in.]
2007: Evolutionary and biomedical insights from the Rhesus macaque genome. Rhesus Macaque Genome Sequencing and Analysis Consortium.
The macaque genome paper: I participated in the PGI experiments that were used to infer segmental duplications and ancestral states. (Even the local paper - La Presse - covered my work, albeit with a bit of exaggeration, see the enclosed Précision :)
Science cover page Science, 316(5822):222-234, 2007. doi:10.1126/science.1139247. La Presse correction
2006: Insights into social insects from the genome of the honey bee Apis mellifera. The Honey Bee Genome Sequencing Consortium.
The honey bee genome paper: I participated in the early BAC-based shotgun sequencing.
Nature cover page Nature, 443:931-949, 2006. doi:10.1038/nature05260.
2005: Pooled Genomic Indexing of Rhesus macaque. Aleksandar Milosavljevic, Ronald A. Harris, Erica J. Sodergren, Andrew R. Jackson, Ken J. Kalafus, Anne Hodgson, Andrew Cree, Miklós Csűrös, Baoli Zhu, Pieter J. de Jong, George M. Weinstock, and Richard A. Gibbs.
Experimental validation of PGI. PGI has been used to map a total of 3858 BAC clones covering approximately 24% of the Rhesus macaque genome to the positions of 4,178 homologous loci in the human genome. A number of intrachromosomal rearrangements were detected by mapping multiple segments within the individual rhesus BACs onto multiple disjoint loci in the human genome.
Genome Research, 15(2):292-301, 2005. doi:10.1101/gr.3162505.
WWW Project webpage at Baylor College of Medicine.
2004: Pooled genomic indexing (PGI): analysis and design of experiments. Miklós Csűrös and Aleksandar Milosavljevic.
Journal of Computational Biology, 11(5): 1001-1021, 2004. doi:10.1089/cmb.2004.11.1001.
PDF Preprint.
2003: Clone-array pooled shotgun mapping and sequencing: design and analysis of experiments. Miklós Csűrös, Bingshan Li and Aleksandar Milosavljevic.
Describes CAPS-MAP and an analysis of CAPSS (Cai et al. 2002).
GIW 2003 - Fourteenth International Conference on Genome Informatics. In Genome Informatics, vol. 14, 186-195.
PDF Extended abstract.
PDF Full version.
q-bio/0312017 Preprint at arXiv.
2003: Shotgun sequencing, clone pooling, and comparative strategies for mapping and sequencing. Aleksandar Milosavljevic, Miklós Csűrös, George Weinstock and Richard A. Gibbs.
Overview and comparison of methods that rely on pooled shotgun sequences: CAPSS, PGI, CAPS-MAP, ST-PGI.
TARGETS (now Drug Discovery Today: TARGETS), 2(6): 245-252, 2003. doi:10.1016/S1477-3627(03)02379-1.
2002: Pooled genomic indexing (PGI): mathematical analysis and experiment design. Miklós Csűrös and Aleksandar Milosavljevic.
First proposal and analysis for PGI.
WABI 2002 - Second International Workshop on Algorithms in Bioinformatics, 10-28, Springer LNCS 2452.
PDF Preprint.

Biological sequence analysis

2007: Reconsidering the significance of genomic word frequencies. Miklós Csűrös, Laurent Noé and Gregory Kucherov.
The frequency of oligonucleotides in a genomic sequence follows primarily a Pareto-lognormal distribution. Lognormal and power-law features found across all known genomes may be the result of completely random evolution by a copying process.
Trends in Genetics, 23(11):543-546, 2007. doi:10.1016/j.tig.2007.07.008.
PDF Preprint.
WWW Supplementary material & software download page.
q-bio/0609022 Earlier version at arXiv.
2007: Rapid homology search with neighbor seeds. Miklós Csűrös and Bin Ma.
Best heuristic local alignment method for DNA sequences.
Algorithmica, 48(2):187-202, 2007. doi:10.1007/s00453-007-0062-y.
PDF Preprint.
2006: Segmentation with an isochore distribution. Miklós Csűrös, Ming-Te Cheng, Andreas Grimm, Amine Halawani and Perrine Landreau.
Segmentation without HMM: uniform distribution over segmentations in which segments have a minimum length.
WABI 2006 - Sixth Workshop on Algorithms in Bioinformatics, 388-399, 2006. Springer LNBI 4175. doi:10.1007/11851561_36.
PDF Preprint.
WWW Supplement - isochore annotation of human chromosome 19 (build hg17/hg18).
2005: Rapid homology search with two-stage extension and daughter seeds. Miklós Csűrös and Bin Ma.
Some memory-efficient techniques that achieve unparalleled speed and sensitivity in seeded alignments.
COCOON 2005 - Eleventh International Computing and Combinatorics Conference, 104-114, 2005. Springer LNCS 3595. doi:10.1007/11533719_13.
PDF Preprint.
2004: Performing local similarity searches with variable length seeds. Miklós Csűrös.
A method for fine-level control of specificity and sensitivity in BLAST-like searches, based on seed trees.
CPM 2004 - Fifteenth Annual Symposium on Combinatorial Pattern Matching, 373-387, 2004. Springer LNCS 3109.
PDF Preprint.
PDF Presentation.
2004: Maximum-scoring segment sets. Miklós Csűrös.
Fast algorithms for change point estimation, post-processing of sequence alignments, and molecular sequence segmentation. RNase P RNA gene in Sulfolobus tokodaii.
IEEE/ACM Transactions on Computational Biology and Bioinformatics, 1(4):139-150, 2004. doi:10.1109/TCBB.2004.4.
PDF Preprint.
2004: Algorithms for finding maximal-scoring segment sets. Miklós Csűrös.
Conference abstract of the above paper.
WABI 2004 - Fourth Workshop on Algorithms in Bioinformatics, 62-73, 2004. Springer LNCS 3240.
PDF Preprint.

None of the above

2010: Approximate counting with a floating-point counter. Miklós Csűrös.
A better method for approximate counting, invented by Morris. Using d+lg lg n+o(1) bits, it is possible to count up to n, with a standard deviation of about 0.6n2-d/2 in the estimate.
COCOON 2010 - Sixteenth International Computing and Combinatorics Conference, to appear.
CS.DS/0904.3062 Preprint at arXiv.
Postscript. Fun version of the preprint: the plots are generated randomly in the printer.
PDF. Frozen version of the preprint.
2005: Single-user tracing and disjointly superimposed codes. Miklós Csűrös and Miklós Ruszinkó.
Extremal properties of pooling designs (aka superimposed codes) used in PGI. Vera Asodi and the great Noga Alon have since improved our asymptotic bounds on family size.
IEEE Transactions on Information Theory, 51(4):1606-1611, 2005. doi:10.1109/TIT.2005.844097.
PDF Preprint.
2004: Single user tracing superimposed codes. Miklós Csűrös and Miklós Ruszinkó.
One-page conference abstract of the above paper.
ISIT 2004 - IEEE International Symposium on Information Theory, page 255. doi:10.1109/ISIT.2004.1365290.
PDF Preprint.
1997: Learning Markov chains with variable memory length from noisy output. Dana Angluin and Miklós Csűrös.
How to construct variable length Markov chains (or amnesiac automata in Ron et al. 1996) from sample sequences received through a noisy channel. The automata can then be used for correcting errors.
COLT 1997 - Tenth Annual Conference on Computational Learning Theory, 298-308, 1997. doi:10.1145/267460.267517.
PostScript Preprint.
1997: Learning variable length Markov chains from noisy output. Miklós Csűrös.
Extended version of the COLT paper.
PostScript Research report

Coauthors

My Erdős number is two, but so is more than 8000 other people's. I am at collaboration distance [at most] four from some other famous people, including Albert Einstein, Bill Gates, Andrei Kolmogorov, Luc Devroye and Gábor Lugosi. I am at distance [at most] eight from Ahmad Chalabi.

Copyright notice

I foolishly transferred the copyrights of some conference and journal publications to the publishers before the current open-access craze. Some of them let me keep the preprints online, some of them don't. In any case, don't copy them beyond fair use. Formally: Preprints are presented here to ensure timely dissemination of scholarly and technical work. These works may not be redistributed without the explicit permission of the copyright holder. Copyright holders other than myself for articles with downloadable preprints are listed below.