Aligning Sequences by Minimum Description Length. (2nd January 2008)

• Record Type: Journal Article
• Authors: Conery, John S.
• Other Names: Grünwald Peter Academic Editor.
• Is Part Of: EURASIP journal on bioinformatics and systems biology. Volume 2007(2007)
• Publication Date: 2008-01-02
• Subjects: Bioinformatics -- Periodicals; Systems biology -- Periodicals; Systems Biology; Signal Processing, Computer-Assisted; Bio-informatique; Biologie systémique; Bioinformatics; Systems biology; Systems Biology; Bioinformatics; Electronic journals; Periodical; Fulltext; Internet Resources; Periodicals; Periodicals; 570.285
• DOI: 10.1155/2007/72936
• Languages: English
• ISSNs: 1687-4145

Abstract

Abstract : This paper presents a new information theoretic framework for aligning sequences in bioinformatics. A transmitter compresses a set of sequences by constructing a regular expression that describes the regions of similarity in the sequences. To retrieve the original set of sequences, a receiver generates all strings that match the expression. An alignment algorithm uses minimum description length to encode and explore alternative expressions; the expression with the shortest encoding provides the best overall alignment. When two substrings contain letters that are similar according to a substitution matrix, a code length function based on conditional probabilities defined by the matrix will encode the substrings with fewer bits. In one experiment, alignments produced with this new method were found to be comparable to alignments fromCLUSTALW . A second experiment measured the accuracy of the new method on pairwise alignments of sequences from the BAliBASE alignment benchmark.