Skip to Main content Skip to Navigation
Journal articles

Orphan gene finding - An exon assembly approach

Philippe Blayo Pierre Rouzé Marie-France Sagot 1, 2 
1 HELIX - Computer science and genomics
Inria Grenoble - Rhône-Alpes, LBBE - Laboratoire de Biométrie et Biologie Evolutive - UMR 5558
2 Baobab
PEGASE - Département PEGASE [LBBE]
Abstract : This paper introduces an algorithm for finding eukaryotic genes. It particularly addresses the problem of orphan genes, that is of genes that cannot, based on homology alone, be connected to any known gene family and to which it is therefore not possible to apply traditional gene finding methods. To the best of our knowledge, this is also the first algorithm that attempts to compare in an exact way two DNA sequences that contain both coding (i.e. exonic) and non-coding (i.e. intronic and, possibly, intergenic) parts. The comparison is performed following an algorithmical model of a gene that is as close as possible to the biological one (we consider in this paper the “one ORF, one gene” problem only). A gene is seen as a set of exons that are pieces of an assembly and are not independent. The algorithm is efficient enough: although the constants are higher than for usual sequence comparison, its time complexity is proportional to the product of the sequences lengths while its space complexity scales linearly with the length of the smallest sequence.
Document type :
Journal articles
Complete list of metadata
Contributor : Marie-France Sagot Connect in order to contact the contributor
Submitted on : Tuesday, September 6, 2011 - 3:16:34 PM
Last modification on : Sunday, September 25, 2022 - 3:57:14 AM


  • HAL Id : hal-00427367, version 2



Philippe Blayo, Pierre Rouzé, Marie-France Sagot. Orphan gene finding - An exon assembly approach. Theoretical Computer Science, Elsevier, 2003, 290 (1), pp.1407-1431. ⟨hal-00427367v2⟩



Record views