Early in the game's development -- when it existed as nothing more than a tech demo, even -- Uncharted existed differently than what we've come to know.
Evan Wells, the co-president of Naughty Dog, recently revealed that the setting of an early iteration of Uncharted took place in an underwater facility. The comparison to Bioshock comes from Wells himself, who notes that it's curious that he's heard Ken Levine say that the setting of one of the early concepts for Bioshock was a tropical island.
That tech demo with the underwater facility was what Naughty Dog used to pitch the Uncharted to Sony. The rest, as they say, is history.