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: genotype inference from mapped sequencing reads in four genomes
Count: gene family evolution and analysis of numerical phylogenetic profiles
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.
- 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.
- 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.
- [Review article]
- WIREs RNA, 4:93-105, 2013. doi:10.1002/wrna.1143 (open access)
- 2012: Origin and evolution of spliceosomal introns
- [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.
- 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.
- →
Video on YouTube.
- 2011: A late origin of the extant eukaryotic diversity: divergence time estimates using rare genomic changes.
- 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.
- [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.
- 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.
- 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.
- 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.
- 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.
- [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. .
- 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. .
- 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. .
- 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. .
- 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.
- [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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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
- 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.
- 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.
- 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. .
- 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, 316(5822):222-234, 2007. doi:10.1126/science.1139247.
- 2006: Insights into social insects from the genome of the honey bee Apis mellifera. .
- The honey bee genome paper: I participated in the early BAC-based shotgun sequencing.
-
Nature, 443:931-949, 2006. doi:10.1038/nature05260.
- 2005: Pooled Genomic Indexing of Rhesus macaque.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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. .
- 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.
- 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.
- 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.
- 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.
- Extended version of the COLT paper.
- →PostScript Research report
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.
- Bioinformatics: © Oxford University Press
- Trends. Genet.: © Elsevier.
- ISIT, IEEE Transactions: © IEEE.
- COCOON, CPM, RECOMB CG, WABI, RECOMB 2006: © Springer-Verlag
- SODA, SICOMP: © Society for Industrial and Applied Mathematics
- COLT, RECOMB 2001: © ACM, Inc.
- J. Comput. Biol.: © Ann Liebert, Inc.