| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Bioinformatics, Vol 15, 211-218, Copyright © 1999 by Oxford University Press
B Morgenstern
MOTIVATION: The performance and time complexity of an improved version of
the segment-to-segment approach to multiple sequence alignment is
discussed. In this approach, alignments are composed from gap-free segment
pairs, and the score of an alignment is defined as the sum of so-called
weights of these segment pairs. RESULTS: A modification of the weight
function used in the original version of the alignment program DIALIGN has
two important advantages: it can be applied to both globally and locally
related sequence sets, and the running time of the program is considerably
improved. The time complexity of the algorithm is discussed theoretically,
and the program running time is reported for various test examples.
AVAILABILITY: The program is available on- line at the Bielefeld University
Bioinformatics Server (BiBiServ)
http://bibiserv.TechFak.Uni-Bielefeld.DE/dial ign/
ARTICLES
DIALIGN 2: improvement of the segment-to-segment approach to multiple sequence alignment
GSF - National Research Center for Environment and Health, Institute of Biomathematics and Biometry, Ingolstadter Landstrasse 1, 85764 Neuherberg, Germany. burkhard.morgenstern@rp-rorer.co.uk
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  K. Ruprecht, H. Ferreira, A. Flockerzi, S. Wahl, M. Sauter, J. Mayer, and N. Mueller-Lantzsch Human Endogenous Retrovirus Family HERV-K(HML-2) RNA Transcripts Are Selectively Packaged into Retroviral Particles Produced by the Human Germ Cell Tumor Line Tera-1 and Originate Mainly from a Provirus on Chromosome 22q11.21 J. Virol., October 15, 2008; 82(20): 10008 - 10016. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 A. R. Gruber, C. Kilgus, A. Mosig, I. L. Hofacker, W. Hennig, and P. F. Stadler Arthropod 7SK RNA Mol. Biol. Evol., September 1, 2008; 25(9): 1923 - 1930. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 K. Katoh and H. Toh Recent developments in the MAFFT multiple sequence alignment program Brief Bioinform, July 1, 2008; 9(4): 286 - 298. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 A. Fontaine, A. de Monte, and H. Touzet MAGNOLIA: multiple alignment of protein-coding and structural RNA sequences Nucleic Acids Res., July 1, 2008; 36(suppl_2): W14 - W18. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 A. D. Kern and D. J. Begun Recurrent Deletion and Gene Presence/Absence Polymorphism: Telomere Dynamics Dominate Evolution at the Tip of 3L in Drosophila melanogaster and D. simulans Genetics, June 1, 2008; 179(2): 1021 - 1027. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
A. Sczyrba, S. Konermann, and R. Giegerich Two interactive Bioinformatics courses at the Bielefeld University Bioinformatics Server Brief Bioinform, May 1, 2008; 9(3): 243 - 249. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
C. G. Artieri, W. Haerty, B. P. Gupta, and R. S. Singh Sexual Selection and Maintenance of Sex: Evidence from Comparisons of Rates of Genomic Accumulation of Mutations and Divergence of Sex-Related Genes in Sexual and Hermaphroditic Species of Caenorhabditis Mol. Biol. Evol., May 1, 2008; 25(5): 972 - 979. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 J.-H. Kim, P. N. Bogner, S.-H. Baek, N. Ramnath, P. Liang, H.-R. Kim, C. Andrews, and Y.-M. Park Up-Regulation of Peroxiredoxin 1 in Lung Cancer and Its Implication as a Prognostic and Therapeutic Target Clin. Cancer Res., April 15, 2008; 14(8): 2326 - 2333. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
D. Houzelstein, I. R. Goncalves, A. Orth, F. Bonhomme, and P. Netter Lgals6, a 2-Million-Year-Old Gene in Mice: A Case of Positive Darwinian Selection and Presence/Absence Polymorphism Genetics, March 1, 2008; 178(3): 1533 - 1545. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 G. Lunter, A. Rocco, N. Mimouni, A. Heger, A. Caldeira, and J. Hein Uncertainty in homology inferences: Assessing and improving genomic sequence alignment Genome Res., February 1, 2008; 18(2): 298 - 309. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 K. M. Wong, M. A. Suchard, and J. P. Huelsenbeck Alignment Uncertainty and Genomic Analysis Science, January 25, 2008; 319(5862): 473 - 476. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 S. Wang, R. R. Gutell, and D. P. Miranker Biclustering as a method for RNA local multiple sequence alignment Bioinformatics, December 15, 2007; 23(24): 3289 - 3296. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
J. E. Mank, L. Hultin-Rosenberg, E. Axelsson, and H. Ellegren Rapid Evolution of Female-Biased, but Not Male-Biased, Genes Expressed in the Avian Brain Mol. Biol. Evol., December 1, 2007; 24(12): 2698 - 2706. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
Y.-S. Chung, W.-H. Lee, C. Y. Tang, and C. L. Lu RE-MuSiC: a tool for multiple sequence alignment with regular expression constraints Nucleic Acids Res., July 13, 2007; 35(suppl_2): W639 - W644. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
S. Moretti, F. Armougom, I. M. Wallace, D. G. Higgins, C. V. Jongeneel, and C. Notredame The M-Coffee web server: a meta-method for computing multiple sequence alignments by combining alternative alignment methods Nucleic Acids Res., July 13, 2007; 35(suppl_2): W645 - W648. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 D. Nakunst, C. Larisch, A. T. Huser, A. Tauch, A. Puhler, and J. Kalinowski The Extracytoplasmic Function-Type Sigma Factor SigM of Corynebacterium glutamicum ATCC 13032 Is Involved in Transcription of Disulfide Stress-Related Genes J. Bacteriol., July 1, 2007; 189(13): 4696 - 4707. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
A. J. Gentles, M. J. Wakefield, O. Kohany, W. Gu, M. A. Batzer, D. D. Pollock, and J. Jurka Evolutionary dynamics of transposable elements in the short-tailed opossum Monodelphis domestica Genome Res., July 1, 2007; 17(7): 992 - 1004. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 A. M. Bojesen, J. Larsen, A. G. Pedersen, T. Morner, R. Mattson, and M. Bisgaard IDENTIFICATION OF A NOVEL MANNHEIMIA GRANULOMATIS LINEAGE FROM LESIONS IN ROE DEER (CAPREOLUS CAPREOLUS) J. Wildl. Dis., July 1, 2007; 43(3): 345 - 352. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
D. M. Held, J. D. Kissel, S. J. Thacker, D. Michalowski, D. Saran, J. Ji, R. W. Hardy, J. J. Rossi, and D. H. Burke Cross-Clade Inhibition of Recombinant Human Immunodeficiency Virus Type 1 (HIV-1), HIV-2, and Simian Immunodeficiency Virus SIVcpz Reverse Transcriptases by RNA Pseudoknot Aptamers J. Virol., May 15, 2007; 81(10): 5375 - 5384. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 M. Klint, H.-H. Fuxelius, R. R. Goldkuhl, H. Skarin, C. Rutemark, S. G. E. Andersson, K. Persson, and B. Herrmann High-Resolution Genotyping of Chlamydia trachomatis Strains by Multilocus Sequence Analysis J. Clin. Microbiol., May 1, 2007; 45(5): 1410 - 1414. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
J. E. Mank, E. Axelsson, and H. Ellegren Fast-X on the Z: Rapid evolution of sex-linked genes in birds Genome Res., May 1, 2007; 17(5): 618 - 624. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
K. Hanekamp, U. Bohnebeck, B. Beszteri, and K. Valentin PhyloGena a user-friendly system for automated phylogenetic annotation of unknown sequences Bioinformatics, April 1, 2007; 23(7): 793 - 801. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
S. Kumar and A. Filipski Multiple sequence alignment: In pursuit of homologous DNA positions Genome Res., February 1, 2007; 17(2): 127 - 135. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 L. Rohmer, M. Brittnacher, K. Svensson, D. Buckley, E. Haugen, Y. Zhou, J. Chang, R. Levy, H. Hayden, M. Forsman, et al. Potential Source of Francisella tularensis Live Vaccine Strain Attenuation Determined by Genome Comparison Infect. Immun., December 1, 2006; 74(12): 6895 - 6906. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
A. F. Barbet, A. M. Lundgren, A. R. Alleman, S. Stuen, A. Bjoersdorff, R. N. Brown, N. L. Drazenovich, and J. E. Foley Structure of the Expression Site Reveals Global Diversity in MSP2 (P44) Variants in Anaplasma phagocytophilum Infect. Immun., November 1, 2006; 74(11): 6429 - 6437. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
D. C. Presgraves Intron Length Evolution in Drosophila Mol. Biol. Evol., November 1, 2006; 23(11): 2203 - 2213. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
M. Rampp, T. Soddemann, and H. Lederer The MIGenAS integrated bioinformatics toolkit for web-based sequence analysis. Nucleic Acids Res., July 1, 2006; 34(Web Server issue): W15 - W19. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 A. Bakhrat, K. Baranes, O. Krichevsky, I. Rom, G. Schlenstedt, S. Pietrokovski, and D. Raveh Nuclear Import of Ho Endonuclease Utilizes Two Nuclear Localization Signals and Four Importins of the Ribosomal Import System J. Biol. Chem., May 5, 2006; 281(18): 12218 - 12226. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
K. Thornton, D. Bachtrog, and P. Andolfatto X chromosomes and autosomes evolve at similar rates in Drosophila: No evidence for faster-X protein evolution Genome Res., April 1, 2006; 16(4): 498 - 504. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
W. Li and A. Godzik VISSA: a program to visualize structural features from structure sequence alignment Bioinformatics, April 1, 2006; 22(7): 887 - 888. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
I. M. Wallace, O. O'Sullivan, D. G. Higgins, and C. Notredame M-Coffee: combining multiple sequence alignment methods with T-Coffee Nucleic Acids Res., March 23, 2006; 34(6): 1692 - 1699. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
W. Huang, D. M. Umbach, and L. Li Accurate anchoring alignment of divergent sequences Bioinformatics, January 1, 2006; 22(1): 29 - 34. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
P. Lockhart, P. Novis, B. G. Milligan, J. Riden, A. Rambaut, and T. Larkum Heterotachy and Tree Building: A Case Study with Plastids and Eubacteria Mol. Biol. Evol., January 1, 2006; 23(1): 40 - 45. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
T. Lassmann and E. L. L. Sonnhammer Automatic assessment of alignment quality Nucleic Acids Res., December 16, 2005; 33(22): 7120 - 7128. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
T. Hindemitt and K. F. X. Mayer CREDO: a web-based tool for computational detection of conserved sequence motifs in noncoding sequences Bioinformatics, December 1, 2005; 21(23): 4304 - 4306. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
L. Charles, I. Carbone, K. G. Davies, D. Bird, M. Burke, B. R. Kerry, and C. H. Opperman Phylogenetic Analysis of Pasteuria penetrans by Use of Multiple Genetic Loci J. Bacteriol., August 15, 2005; 187(16): 5700 - 5708. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 N. Kouprina, A. Pavlicek, N. K. Collins, M. Nakano, V. N. Noskov, J.-I. Ohzeki, G. H. Mochida, J. I. Risinger, P. Goldsmith, M. Gunsior, et al. The microcephaly ASPM gene is expressed in proliferating tissues and encodes for a mitotic spindle protein Hum. Mol. Genet., August 1, 2005; 14(15): 2155 - 2165. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
M. Frenkel-Morgenstern, A. Singer, H. Bronfeld, and S. Pietrokovski One-Block CYRCA: an automated procedure for identifying multiple-block alignments from single block queries Nucleic Acids Res., July 1, 2005; 33(suppl_2): W281 - W283. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
S. Roepcke, S. Grossmann, S. Rahmann, and M. Vingron T-Reg Comparator: an analysis tool for the comparison of position weight matrices Nucleic Acids Res., July 1, 2005; 33(suppl_2): W438 - W441. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
D. Pohler, N. Werner, R. Steinkamp, and B. Morgenstern Multiple alignment of genomic sequences using CHAOS, DIALIGN and ABC Nucleic Acids Res., July 1, 2005; 33(suppl_2): W532 - W534. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 S. E. Abdel-Ghany, I. S. Day, M. P. Simmons, P. Kugrens, and A. S.N. Reddy Origin and Evolution of Kinesin-Like Calmodulin-Binding Protein Plant Physiology, July 1, 2005; 138(3): 1711 - 1722. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
C. L. Lu, T. C. Wang, Y. C. Lin, and C. Y. Tang ROBIN: a tool for genome rearrangement of block-interchanges Bioinformatics, June 1, 2005; 21(11): 2780 - 2782. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
C. Carrillo, E. R. Tulman, G. Delhon, Z. Lu, A. Carreno, A. Vagnozzi, G. F. Kutish, and D. L. Rock Comparative Genomics of Foot-and-Mouth Disease Virus J. Virol., May 15, 2005; 79(10): 6487 - 6504. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
R. G. Beiko, C. X. Chan, and M. A. Ragan A word-oriented approach to alignment validation Bioinformatics, May 15, 2005; 21(10): 2230 - 2239. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 W. R. Atchley and A. D. Fernandes Sequence signatures and the probabilistic identification of proteins in the Myc-Max-Mad network PNAS, May 3, 2005; 102(18): 6401 - 6406. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
T. D. Wu and C. K. Watanabe GMAP: a genomic mapping and alignment program for mRNA and EST sequences Bioinformatics, May 1, 2005; 21(9): 1859 - 1875. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
Y. Nozaki and M. Bellgard Statistical evaluation and comparison of a pairwise alignment algorithm that a priori assigns the number of gaps rather than employing gap penalties Bioinformatics, April 15, 2005; 21(8): 1421 - 1428. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
B. Morgenstern, N. Werner, S. J. Prohaska, R. Steinkamp, I. Schneider, A. R. Subramanian, P. F. Stadler, and J. Weyer-Menkhoff Multiple sequence alignment with user-defined constraints at GOBICS Bioinformatics, April 1, 2005; 21(7): 1271 - 1273. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
A. Flockerzi, S. Burkhardt, W. Schempp, E. Meese, and J. Mayer Human Endogenous Retrovirus HERV-K14 Families: Status, Variants, Evolution, and Mobilization of Other Cellular Sequences J. Virol., March 1, 2005; 79(5): 2941 - 2949. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
Y. Zhang and M. S. Waterman An Eulerian path approach to local multiple alignment for DNA sequences PNAS, February 1, 2005; 102(5): 1285 - 1290. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 V. J. Yao, M. G. Ozawa, M. Trepel, W. Arap, D. M. McDonald, and R. Pasqualini Targeting Pancreatic Islets with Phage Display Assisted by Laser Pressure Catapult Microdissection Am. J. Pathol., February 1, 2005; 166(2): 625 - 636. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
C. Lohne and T. Borsch Molecular Evolution and Phylogenetic Utility of the petD Group II Intron: A Case Study in Basal Angiosperms Mol. Biol. Evol., February 1, 2005; 22(2): 317 - 332. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
L. Ye and X. Huang MAP2: multiple alignment of syntenic genomic sequences Nucleic Acids Res., January 7, 2005; 33(1): 162 - 170. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
N. Hosoya-Matsuda, K. Motohashi, H. Yoshimura, A. Nozaki, K. Inoue, M. Ohmori, and T. Hisabori Anti-oxidative Stress System in Cyanobacteria: SIGNIFICANCE OF TYPE II PEROXIREDOXIN AND THE ROLE OF 1-Cys PEROXIREDOXIN IN SYNECHOCYSTIS SP. STRAIN PCC 6803 J. Biol. Chem., January 7, 2005; 280(1): 840 - 846. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
E. Barta, E. Sebestyen, T. B. Palfy, G. Toth, C. P. Ortutay, and L. Patthy DoOP: Databases of Orthologous Promoters, collections of clusters of orthologous upstream sequences from chordates and plants Nucleic Acids Res., January 1, 2005; 33(suppl_1): D86 - D90. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
C. L. Lu and Y. P. Huang A memory-efficient algorithm for multiple sequence alignment with constraints Bioinformatics, January 1, 2005; 21(1): 20 - 30. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
T. Meinel, A. Krause, H. Luz, M. Vingron, and E. Staub The SYSTERS Protein Family Database in 2005 Nucleic Acids Res., January 1, 2005; 33(suppl_1): D226 - D229. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
A. D. Kern and D. J. Begun Patterns of Polymorphism and Divergence from Noncoding Sequences of Drosophila melanogaster and D. simulans: Evidence for Nonequilibrium Processes Mol. Biol. Evol., January 1, 2005; 22(1): 51 - 62. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
I. G. Bravo and A. Alonso Mucosal Human Papillomaviruses Encode Four Different E5 Proteins Whose Chemistry and Phylogeny Correlate with Malignant or Benign Growth J. Virol., December 15, 2004; 78(24): 13613 - 13626. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
J. R. Mathias, S. E. Hanlon, R. A. O'Flanagan, A. M. Sengupta, and A. K. Vershon Repression of the yeast HO gene by the MAT{alpha}2 and MATa1 homeodomain proteins Nucleic Acids Res., December 14, 2004; 32(22): 6469 - 6478. [Abstract] |