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. |
Year | DOI | Venue |
---|---|---|
2015 | 10.1007/978-3-319-20086-6_19 | SEA |
DocType | Volume | ISSN |
Conference | 9125 | 0302-9743 |
Citations | PageRank | References |
5 | 0.43 | 16 |
Authors | ||
6 |
Name | Order | Citations | PageRank |
---|---|---|---|
Carl Barton | 1 | 84 | 11.07 |
Costas S. Iliopoulos | 2 | 1534 | 167.43 |
Ritu Kundu | 3 | 17 | 3.76 |
Solon P. Pissis | 4 | 281 | 57.09 |
Ahmad Retha | 5 | 16 | 2.98 |
Fatima Vayani | 6 | 25 | 3.85 |