|
| << vorige | volgende >> |
Tijdschrift beschrijving
Alle jaargangen van het bijbehorende tijdschrift
Alle afleveringen van het bijbehorende jaargang
Alle artikelen van de bijbehorende aflevering
Details van artikel 23 van 25 gevonden artikelen
| Titel: |
The Shortest Common Superstring Problem and Viral Genome Compression |
| Auteur: |
Ilie, Lucian Popescu, Cristian |
| Verschenen in: |
Fundamenta informaticae |
| Paginering: | Jaargang 73 (2006) nr. 1-2 pagina's 153-164 |
| Jaar: |
2006-08-28 |
| Inhoud: |
Viruses compress their genome to reduce space. One of the main techniques is overlapping genes. We model this process by the shortest common superstring problem. We give an algorithm for computing optimal solutions which is slow in the number of strings but fast (linear) in their total length. This algorithm is used for a number of viruses with relatively few genes. When the number of genes is larger, we compute approximate solutions using the greedy algorithm which gives an upper bound for the optimal solution. We give also a lower bound for the shortest common superstring problem. The results obtained are then compared with what happens in nature. Remarkably, the compression obtained by viruses is very close to the one achieved by modern computers. |
| Uitgever: |
IOS Press |
| Bronbestand: |
Elektronische Wetenschappelijke Tijdschriften |
Details van artikel 23 van 25 gevonden artikelen
| << vorige | volgende >> |