Accurate and efficient methods to improve multiple circular sequence alignment

Research output: Chapter in Book/Report/Conference proceedingChapterpeer-review

16 Citations (Scopus)


Multiple sequence alignment is a core computational task in bioinformatics and has been extensively studied over the past decades. This computation requires an implicit assumption on the input data: the left- and right-most position for each sequence is relevant. However, this is not the case for circular structures; for instance, MtDNA. Efforts have been made to address this issue but it is far from being solved. We have very recently introduced a fast algorithm for approximate circular string matching (Barton et al., Algo Mol Biol, 2014). Here, we first show how to extend this algorithm for approximate circular dictionary matching; and, then, apply this solution with agglomerative hierarchical clustering to find a sufficiently good rotation for each sequence. Furthermore, we propose an alternative method that is suitable for more divergent sequences. We implemented these methods in BEAR, a programme for improving multiple circular sequence alignment. Experimental results, using real and synthetic data, show the high accuracy and efficiency of these new methods in terms of the inferred likelihood-based phylogenies.
Original languageEnglish
Title of host publicationExperimental Algorithms
Subtitle of host publication14th International Symposium, SEA 2015, Paris, France, June 29 – July 1, 2015, Proceedings
EditorsE. Bampis
PublisherSpringer International Publishing Switzerland
Number of pages12
ISBN (Electronic)9783319200866
ISBN (Print)9783319200859
Publication statusPublished - 20 Jun 2015

Publication series

NameLecture Notes in Computer Science
PublisherSpringer International Publishing Switzerland


Dive into the research topics of 'Accurate and efficient methods to improve multiple circular sequence alignment'. Together they form a unique fingerprint.

Cite this