| 1. |
- Birin, Hadas, et al.
(författare)
-
Inferring models of rearrangements, recombinations, and horizontal transfers by the minimum evolution criterion
- 2007
-
Ingår i: Algorithms in Bioinformatics, Proceedings. - Berlin, Heidelberg : Springer Berlin Heidelberg. - 9783540741251 ; , s. 111-123
-
Konferensbidrag (refereegranskat)abstract
- The evolution of viruses is very rapid and in addition to local point mutations (insertion, deletion, substitution) it also includes frequent recombinations, genome rearrangements, and horizontal transfer of genetic material. Evolutionary analysis of viral sequences is therefore a complicated matter for two main reasons: First, due to HGTs and recombinations, the right model of evolution is a network and not a tree. Second, due to genome rearrangements, an alignment of the input sequences is not guaranteed. Since contemporary methods for inferring phylogenetic networks require aligned sequences as input, they cannot deal with viral evolution. In this work we present the first computational approach which deals with both genome rearrangements and horizontal gene transfers and does not require a multiple alignment as input. We formalize a new set of computational problems which involve analyzing such complex models of evolution, investigate their computational complexity, and devise algorithms for solving them. Moreover, we demonstrate the viability of our methods on several synthetic datasets as well as biological datasets.
|
|
| 2. |
- Ilie, Lucian, et al.
(författare)
-
Fast computation of good multiple spaced seeds
- 2007
-
Ingår i: Algorithms in Bioinformatics, Proceedings (Lecture Notes in Computer Science). - Berlin, Heidelberg : Springer Berlin Heidelberg. - 0302-9743 .- 1611-3349. - 9783540741251 ; 4645, s. 346-358
-
Konferensbidrag (refereegranskat)abstract
- Homology search finds similar segments between two biological sequences, such as DNA or protein sequences. A significant fraction of computing power in the world is dedicated to performing such tasks. The introduction of optimal spaced seeds by Ma et al. has increased both the sensitivity and the speed of homology search and it has been adopted by many alignment programs such as BLAST. With the further improvement provided by multiple spaced seeds in PatternHunterII, the sensitivity of dynamic programming is approached at BLASTn speed. Whereas computing optimal multiple spaced seeds was proved to be NP-hard, we show that, from practical point of view, computing good ones can be very efficient. We give a simple heuristic algorithm which computes good multiple seeds in polynomial time. Computing sensitivity is not required. When allowing the computation of the sensitivity for few seeds, we obtain better multiple seeds than previous ones in much shorter time.
|
|
