Accurate and efficient methods to improve multiple circular sequence alignment

Carl Barton, Costas S. Iliopoulos, Ritu Kundu, Solon P. Pissis*, Ahmad Retha, Fatima Vayani

*Corresponding author for this work

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

Abstract

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 - 14th International Symposium, SEA 2015, Proceedings
EditorsEvripidis Bampis
PublisherSpringer Verlag
Pages247-258
Number of pages12
ISBN (Print)9783319200859
DOIs
Publication statusPublished - 1 Jan 2015
Externally publishedYes
Event14th International Symposium on Experimental Algorithms, SEA 2015 - Paris, France
Duration: 29 Jun 20151 Jul 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9125
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference14th International Symposium on Experimental Algorithms, SEA 2015
CountryFrance
CityParis
Period29/06/151/07/15

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

Cite this