Abstract
Given a multiple alignment over $k$ sequences, an evolutionary tree
relating the sequences, and a subadditive gap penalty function (e.g.
an affine function), we reconstruct the internal nodes of the tree
optimally: we find the optimal explanation in terms of indels
of the observed gaps and find the most parsimonious assignment of
nucleotides. The gaps of the alignment are represented in a
so-called gap graph, and through theoretically sound preprocessing
the graph is reduced to pave the way for a running time which in all
but the most pathological examples is far better than the
exponential worst case time. E.g. for a tree with nine leaves and a
random alignment of length 10.000 with 60% gaps, the running time
is on average around 45 seconds. For a real alignment of length 9868 of
nine HIV-1 sequences, the running time is less than one second.
relating the sequences, and a subadditive gap penalty function (e.g.
an affine function), we reconstruct the internal nodes of the tree
optimally: we find the optimal explanation in terms of indels
of the observed gaps and find the most parsimonious assignment of
nucleotides. The gaps of the alignment are represented in a
so-called gap graph, and through theoretically sound preprocessing
the graph is reduced to pave the way for a running time which in all
but the most pathological examples is far better than the
exponential worst case time. E.g. for a tree with nine leaves and a
random alignment of length 10.000 with 60% gaps, the running time
is on average around 45 seconds. For a real alignment of length 9868 of
nine HIV-1 sequences, the running time is less than one second.
| Original language | English |
|---|---|
| Title of host publication | Proceedings of the 3rd workshop on algorithms in bioinformatics (WABI 2003) |
| Number of pages | 16 |
| Publication date | 2003 |
| Pages | 417-432 |
| Publication status | Published - 2003 |
| Event | Workshop on algorithms in bioinformatics (WABI 2003) - Budapest, Hungary Duration: 17 Dec 2010 → … Conference number: 3 |
Conference
| Conference | Workshop on algorithms in bioinformatics (WABI 2003) |
|---|---|
| Number | 3 |
| Country/Territory | Hungary |
| City | Budapest |
| Period | 17/12/2010 → … |