Skip to Main content Skip to Navigation
Journal articles

Improved search heuristics find 20 000 new alignments between human and mouse genomes.

Abstract : Sequence similarity search is a fundamental way of analyzing nucleotide sequences. Despite decades of research, this is not a solved problem because there exist many similarities that are not found by current methods. Search methods are typically based on a seed-and-extend approach, which has many variants (e.g. spaced seeds, transition seeds), and it remains unclear how to optimize this approach. This study designs and tests seeding methods for inter-mammal and inter-insect genome comparison. By considering substitution patterns of real genomes, we design sets of multiple complementary transition seeds, which have better performance (sensitivity per run time) than previous seeding strategies. Often the best seed patterns have more transition positions than those used previously. We also point out that recent computer memory sizes (e.g. 60 GB) make it feasible to use multiple (e.g. eight) seeds for whole mammal genomes. Interestingly, the most sensitive settings achieve diminishing returns for human-dog and melanogaster-pseudoobscura comparisons, but not for human-mouse, which suggests that we still miss many human-mouse alignments. Our optimized heuristics find ∼20 000 new human-mouse alignments that are missing from the standard UCSC alignments. We tabulate seed patterns and parameters that work well so they can be used in future research.
Complete list of metadata

https://hal.inria.fr/hal-00958207
Contributor : Laurent Noé <>
Submitted on : Tuesday, March 11, 2014 - 10:39:42 PM
Last modification on : Saturday, December 19, 2020 - 11:08:03 AM

Links full text

Identifiers

Citation

Martin Frith, Laurent Noé. Improved search heuristics find 20 000 new alignments between human and mouse genomes.. Nucleic Acids Research, Oxford University Press, 2014, 42 (7), pp.e59. ⟨10.1093/nar/gku104⟩. ⟨hal-00958207⟩

Share

Metrics

Record views

325