Search

The identification of homologous DNA is a fundamental buildingblock of comparative genomic and molecular evolution studies. To date, pairwiselocal sequence alignment methods have been the prevailing technique to identifyhomologous nucleotides. However, existing methods that identify and align allhomologous nucleotides in one or more genomes have suffered poor scalabilityand limited accuracy.We propose a novel method that couples a gapped extensionheuristic with a previously described efficient filtration method for local multiplealignment. During gapped extension, we use the MUSCLE implementation ofprogressive multiple alignment with iterative refinement. The resulting gappedextensions potentially contain alignments of unrelated sequence. We detectand remove such undesirable alignments using a hidden Markov model topredict the posterior probability of homology. The HMM emission frequenciesfor nucleotide substitutions can be derived from any strand/species-symmetric nucleotide substitution matrix, and we have developed a method to adapt anarbitrary substitution matrix (i.e. HOXD) to organisms with different G+Ccontent. We evaluate the performance of our method and previous approacheson a hybrid dataset of real genomic DNA with simulated interspersed repeats.Our method outperforms existing methods in terms of sensitivity, positivepredictive value, and localizing boundaries of homology. The described methodshave been implemented in the free, open-source procrastAligner software,available from: http://alggen.lsi.upc.es/recerca/align/procrastination.

We describe an efficient local multiple alignment filtration heuristic for identification of conserved regions in one or more DNA sequences. The method incorporates several novel ideas: (1) palindromic spaced seed patterns to match both DNA strands simultaneously, (2) seed extension (chaining) in order of decreasing multiplicity, and (3) procrastination when low multiplicity matches are encountered. The resulting local multiple alignments may have nucleotide substitutions and internal gaps as large as w characters in any occurrence of the motif. The algorithm consumes $\mathcal{O}(wN)$ memory and $\mathcal{O}(wN \log wN)$ time where N is the sequence length. We score the significance of multiple alignments using entropy-based motif scoring methods. We demonstrate the performance of our filtration method on Alu-repeat rich segments of the human genome and a large set of Hepatitis C virus genomes. The GPL implementation of our algorithm in C++ is called procrastAligner and is freely available from http://gel.ahabs.wisc.edu/procrastination

We describe a new method for reliably identifying conserved segments among genome sequences that have undergone rearrangement, horizontal transfer, and substantial nucleotide-level divergence. A Gibbs-like sampler explores different combinations of sequence-based markers shared by the genomes under study. The sampler assigns each marker a posterior probability based on how frequently it participates in some collinear group of markers. Markers with high p.p. values are likely members of conserved segments. The method identifies both large-scale and local trends in segmental collinearity, providing suitable input for genome alignment and rearrangement history inference tools. Applying our method to genomes of four Streptococci reveals that rearranged segments in these organisms belong in two size categories: large conserved segments that are interrupted by a staccato of single gene or operon-size small segments. The rearrangement pattern of large segments is best explained by symmetric inversions about the origin of replication while the pattern of small segments is not.