Name
Abstract | ||
|---|---|---|
To facilitate research in comparative genomics, sequencing projects are increasingly aimed at assembling the genomes of closely related organisms. Given two incomplete assemblies of two related genomes, the question arises how to use the similarity of the two sequences to obtain a better ordering and orientation of both assemblies. In this paper, we formalize this question as the Optimal Syntenic Layout problem, show that it is in general NP-hard, but that it can be solved well in practice using an algorithm based on maximal graph matching. We illustrate the problem using different assemblies of two strains of Bdellovibrio bacteriovorus. In this paper we propose a formulation and algorithm for the Optimal Syntenic Layout problem that aims at finding a "syntenic layout" of two assemblies that maximize the number of pairs of extended "local diagonals". Our solution is based on the weighted graph matching problem. Our approach also addresses the important special case in which one of the two genomes is available as a complete sequence, and is used to "syntenically layout" the contigs of the other genome. |
Year | Venue | Keywords |
|---|---|---|
2004 | German Conference on Bioinformatics | comparative genomics,graph matching |
Field | DocType | Citations |
Synteny,Genome,Biology,Bioinformatics | Conference | 0 |
PageRank | References | Authors |
0.34 | 3 | 6 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Olaf Delgado Friedrichs | 1 | 6 | 2.62 |
| Aaron L. Halpern | 2 | 55 | 14.04 |
| Ross Lippert | 3 | 251 | 25.98 |
| Christian Rausch | 4 | 86 | 5.37 |
| Stephan C. Schuster | 5 | 120 | 11.47 |
| Daniel H. Huson | 6 | 765 | 91.20 |