A genome alignment algorithm based on compression
Open Access
- 16 December 2010
- journal article
- Published by Springer Nature in BMC Bioinformatics
- Vol. 11 (1) , 599
Abstract
Traditional genome alignment methods consider sequence alignment as a variation of the string edit distance problem, and perform alignment by matching characters of the two sequences. They are often computationally expensive and unable to deal with low information regions. Furthermore, they lack a well-principled objective function to measure the performance of sets of parameters. Since genomic sequences carry genetic information, this article proposes that the information content of each nucleotide in a position should be considered in sequence alignment. An information-theoretic approach for pairwise genome local alignment, namely XMAligner, is presented. Instead of comparing sequences at the character level, XMAligner considers a pair of nucleotides from two sequences to be related if their mutual information in context is significant. The information content of nucleotides in sequences is measured by a lossless compression technique.Keywords
This publication has 43 references indexed in Scilit:
- Towards realistic benchmarks for multiple alignments of non-coding sequencesBMC Bioinformatics, 2010
- Plasmodium falciparum and Plasmodium vivax: so similar, yet very differentParasitology Research, 2009
- Pairwise statistical significance of local sequence alignment using multiple parameter sets and empirical justification of parameter set change penaltyBMC Bioinformatics, 2009
- Genome bias influences amino acid choices: analysis of amino acid substitution and re-compilation of substitution matrices exclusive to an AT-biased genomeNucleic Acids Research, 2008
- Analyses of deep mammalian sequence alignments and constraint predictions for 1% of the human genomeGenome Research, 2007
- Comparative analysis of long DNA sequences by per element information content using different contextsBMC Bioinformatics, 2007
- Gapped BLAST and PSI-BLAST: a new generation of protein database search programsNucleic Acids Research, 1997
- Statistics of local complexity in amino acid sequences and sequence databasesComputers & Chemistry, 1993
- Basic local alignment search toolJournal of Molecular Biology, 1990
- The information content of a multistate distributionJournal of Theoretical Biology, 1969