title: Computing posterior probabilities for score-based alignments using ppALIGN.
abstract: Score-based pairwise alignments are widely used in         bioinformatics in particular with molecular database search         tools, such as the BLAST family.  Due to sophisticated heuristics,         such algorithms are usually fast but  the         underlying scoring model unfortunately lacks a statistical description of         the reliability of the reported alignments.  In particular,         close to gaps, in low-score or low-complexity         regions, a huge number of alternative alignments arise which         results in a decrease of the certainty of the alignment.          ppALIGN is a software package that uses hidden Markov         Model techniques to compute position-wise reliability of          score-based pairwise alignments of DNA or protein sequences.  The         design of the model allows for a direct connection between the         scoring function and the parameters of the probabilistic         model. For this reason it is suitable to analyze the         outcomes of popular score based aligners and search tools         without having to choose a complicated set of parameters. By contrast, our program         only requires the classical score parameters (the scoring function         and gap costs). The package comes along with a library written         in C++, a standalone program for user defined         alignments (ppALIGN) and another program (ppBLAST)          which can process a complete result set of BLAST.  The main algorithms         essentially exhibit a linear time complexity (in the alignment         lengths), and they are hence suitable for on-line computations.         We have also included alternative decoding algorithms to provide         alternative alignments.                 ppALIGN is a fast         program/library that helps detect and quantify questionable         regions in pairwise alignments.  Due to its structure, the         input/output interface it can to be            connected to other post-processing tools.  Empirically, we illustrate its         usefulness in terms of correctly predicted reliable regions         for sequences generated using the ROSE model for sequence         evolution, and identify sensor-specific         regions in the denitrifying betaproteobacterium         Aromatoleum aromaticum.
authors.affiliation: Department of Applied Mathematics (MAP5), University of Paris Descartes, France.
authors.forename: Stefan
authors.initials: S
authors.lastname: Wolfsheimer
authors.forename: Alexander
authors.initials: A
authors.lastname: Hartmann
authors.forename: Ralf
authors.initials: R
authors.lastname: Rabus
authors.forename: Gregory
authors.initials: G
authors.lastname: Nuel
mesh_terms: D000465:Algorithms; D000595:Amino Acid Sequence; D000818:Animals; D001483:Base Sequence; D019295:Computational Biology / Q000379:methods; D030541:Databases, Genetic; D006801:Humans; D012107:Research Design; D057386:Search Engine; D016415:Sequence Alignment; D012984:Software