title: A novel heuristic for local multiple alignment of interspersed DNA repeats.
abstract: Pairwise local sequence alignment methods have been the prevailing technique to identify homologous nucleotides between related species. However, existing methods that identify and align all homologous nucleotides in one or more genomes have suffered from poor scalability and limited accuracy. We propose a novel method that couples a gapped extension heuristic with an efficient filtration method for identifying interspersed repeats in genome sequences. During gapped extension, we use the MUSCLE implementation of progressive global multiple alignment with iterative refinement. The resulting gapped extensions potentially contain alignments of unrelated sequence. We detect and remove such undesirable alignments using a hidden Markov model (HMM) to predict the posterior probability of homology. The HMM emission frequencies for nucleotide substitutions can be derived from any time-reversible nucleotide substitution matrix. We evaluate the performance of our method and previous approaches on a hybrid data set of real genomic DNA with simulated interspersed repeats. Our method outperforms a related method in terms of sensitivity, positive predictive value, and localizing boundaries of homology. The described methods have been implemented in freely available software, Repeatoire, available from: http://wwwabi.snv.jussieu.fr/public/Repeatoire.
authors.affiliation: Institut Pasteur, CNRS and UPMC University, Paris, France.
authors.forename: Todd J
authors.initials: TJ
authors.lastname: Treangen
authors.forename: Aaron E
authors.initials: AE
authors.lastname: Darling
authors.forename: Guillaume
authors.initials: G
authors.lastname: Achaz
authors.forename: Mark A
authors.initials: MA
authors.lastname: Ragan
authors.forename: Xavier
authors.initials: X
authors.lastname: Messeguer
authors.forename: Eduardo P C
authors.initials: EP
authors.lastname: Rocha
mesh_terms: D001483:Base Sequence; D003198:Computer Simulation; D004247:DNA / Q000737:chemistry*; D004269:DNA, Bacterial / Q000737:chemistry; D016680:Genome, Bacterial; D020071:Interspersed Repetitive Sequences; D008390:Markov Chains; D015233:Models, Statistical; D008969:Molecular Sequence Data; D045704:Mycoplasma genitalium / Q000235:genetics; D016415:Sequence Alignment / Q000379:methods*; D012689:Sequence Homology, Nucleic Acid; D012984:Software
chemical_list: D004269:DNA, Bacterial; D004247:DNA